如果元素 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 是合法分割中的最小下标。
时间: 2024-04-17 17:24:41 浏览: 91
题目描述:给定一个整数数组 nums,其中一个支配元素。要求在数组中找到一个最小的下标 i,使得以 i 为分割点,将数组分割成两个子数组,且两个子数组的支配元素相同。
解答:首先,我们需要找到数组中的支配元素。可以使用摩尔投票算法来实现,具体步骤如下:
1. 初始化一个计数器 count 和一个候选支配元素 candidate。
2. 遍历数组,对于每个元素 num,如果 count 为 0,则将 num 设为 candidate,并将 count 设为 1。
3. 如果 num 等于 candidate,则将 count 的值加 1;否则将 count 的值减 1。
4. 遍历完成后,candidate 即为支配元素。
接下来,我们需要遍历数组,找到分割点 i。我们从左到右遍历数组,维护两个计数器 leftCount 和 rightCount,分别表示左侧子数组和右侧子数组中支配元素的出现次数。
初始时,左侧子数组为空,右侧子数组包含所有元素。我们遍历过程中,将支配元素的出现次数加入 rightCount,同时将支配元素的出现次数从 rightCount 中减去。当 leftCount * 2 > i + 1 且 rightCount * 2 > n - i - 1 时,说明以 i 为分割点的两个子数组都有相同的支配元素,满足条件。
具体实现如下:
```python
def min_split_index(nums):
# 找到支配元素
count, candidate = 0, None
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# 遍历找到分割点
leftCount, rightCount = 0, sum(1 for num in nums if num == candidate)
for i in range(len(nums)):
if leftCount * 2 > i + 1 and rightCount * 2 > len(nums) - i - 1:
return i
if nums[i] == candidate:
leftCount += 1
rightCount -= 1
return -1
```
时间复杂度:摩尔投票算法的时间复杂度为 O(n),遍历找分割点的时间复杂度为 O(n),因此总的时间复杂度为 O(n)。
阅读全文