2780-合法分割的最小下标

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

如果元素 x 在长度为 m 的整数数组 arr 中满足 freq(x) * 2 > m ，那么我们称 x 是 支配元素 。其中
freq(x) 是 x 在数组 arr 中出现的次数。注意，根据这个定义，数组 arr 最多 只会有 一个 支配元素。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。

你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i + 1, ..., n - 1]
，如果一个分割满足以下条件，我们称它是 合法 的：

  • 0 <= i < n - 1
  • nums[0, ..., i] 和 nums[i + 1, ..., n - 1] 的支配元素相同。

这里， nums[i, ..., j] 表示 nums 的一个子数组，它开始于下标 i ，结束于下标 j
，两个端点都包含在子数组内。特别地，如果 j < i ，那么 nums[i, ..., j] 表示一个空数组。

请你返回一个 合法分割 的 最小 下标。如果合法分割不存在，返回 -1 。

示例 1：

**输入：** nums = [1,2,2,2]
**输出：** 2
**解释：** 我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。
数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 > 3 。
数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 > 1 。
两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 2 是合法分割中的最小下标。

示例 2：

**输入：** nums = [2,1,3,1,1,1,7,1,2,1]
**输出：** 4
**解释：** 我们将数组在下标 4 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。
数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 4 是所有合法分割中的最小下标。

示例 3：

**输入：** nums = [3,3,3,3,7,2,2]
**输出：** -1
**解释：** 没有合法分割。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums 有且只有一个支配元素。

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

首先证明：分割出的两个数组的支配元素就是原数组的支配元素。

设这两个数组的支配元素为 y（题目要求支配元素相同），那么对于第一个数组有

\text{freq}_1(y) \cdot 2 > i+1

对于第二个数组有

\text{freq}_2(y) \cdot 2 > n-i-1

由于这两个数组合并之后就是原数组，所以

\text{freq}(y) \cdot 2 = \text{freq}_1(y) \cdot 2 + \text{freq}_2(y) \cdot 2 > (i+1) + (n-i-1) = n

上式表明，y 就是原数组的支配元素，证毕。

算法

首先求出众数 mode 及其出现次数 total。

然后枚举 i，一边枚举一边统计 freq}_1(\textit{mode})，那么 freq}_2(\textit{mode}) =\textit{total} -\text{freq}_1(\textit{mode})。

只要满足 freq}_1(\textit{mode}) \cdot 2 > i+1 且 freq}_2(\textit{mode}) \cdot 2 > n-i-1，就返回 i。

如果没有这样的 i，返回 -1。

[sol-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        mode, total = Counter(nums).most_common(1)[0]
        freq1 = 0
        for i, x in enumerate(nums):
            freq1 += x == mode
            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:
                return i
        return -1
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func minimumIndex(nums []int) int {
	// 也可以用摩尔投票法实现
	freq := map[int]int{}
	mode := nums[0]
	for _, x := range nums {
		freq[x]++
		if freq[x] > freq[mode] {
			mode = x
		}
	}

	total := freq[mode]
	freq1 := 0
	for i, x := range nums {
		if x == mode {
			freq1++
		}
		if freq1*2 > i+1 && (total-freq1)*2 > len(nums)-i-1 {
			return i
		}
	}
	return -1
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(n)。用摩尔投票法可以做到 \mathcal{O}(1) 额外空间。
 Comments
On this page
2780-合法分割的最小下标
  1. 算法