Medium

题目描述

对于长度为 m 的整数数组 arr 中的元素 x，如果 arr 中超过一半的元素的值为 x，则称 x 为 dominant（主导）元素。

给你一个长度为 n 的下标从 0 开始的整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 恰好有一个主导元素。

解题思路

解题思路：

首先理解题意：我们需要找到一个分割点，使得分割后的两个子数组都有相同的主导元素。

解法分析：

  1. 预处理阶段：

    • 使用哈希表统计整个数组中每个元素的出现频率
    • 找到主导元素及其总频率（出现次数超过数组长度的一半）

  2. 遍历分割点：

    • 对于每个可能的分割点 i（0 到 n-2），计算主导元素在左子数组中的频率
    • 右子数组中主导元素的频率 = 总频率 - 左子数组频率
    • 检查主导元素在两个子数组中是否都满足主导条件

  3. 主导条件判断：

    • 对于长度为 len 的子数组，元素频率 > len/2 时该元素为主导元素
    • 等价于：频率 * 2 > len

优化点：

  • 只需要追踪主导元素的频率变化，不需要统计其他元素
  • 一旦找到有效分割点，立即返回（题目要求最小下标）

代码实现

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        int n = nums.size();
        
        // 找到主导元素
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        int dominant = 0, totalFreq = 0;
        for (auto& p : freq) {
            if (p.second * 2 > n) {
                dominant = p.first;
                totalFreq = p.second;
                break;
            }
        }
        
        // 检查每个分割点
        int leftFreq = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == dominant) {
                leftFreq++;
            }
            
            int rightFreq = totalFreq - leftFreq;
            int leftLen = i + 1;
            int rightLen = n - i - 1;
            
            // 检查两个子数组是否都有主导元素
            if (leftFreq * 2 > leftLen && rightFreq * 2 > rightLen) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 找到主导元素
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        
        dominant = 0
        total_freq = 0
        for num, count in freq.items():
            if count * 2 > n:
                dominant = num
                total_freq = count
                break
        
        # 检查每个分割点
        left_freq = 0
        for i in range(n - 1):
            if nums[i] == dominant:
                left_freq += 1
            
            right_freq = total_freq - left_freq
            left_len = i + 1
            right_len = n - i - 1
            
            # 检查两个子数组是否都有主导元素
            if left_freq * 2 > left_len and right_freq * 2 > right_len:
                return i
        
        return -1

public class Solution {
    public int MinimumIndex(IList<int> nums) {
        int n = nums.Count;
        
        // 找到主导元素
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        int dominant = 0, totalFreq = 0;
        foreach (var pair in freq) {
            if (pair.Value * 2 > n) {
                dominant = pair.Key;
                totalFreq = pair.Value;
                break;
            }
        }
        
        // 检查每个分割点
        int leftFreq = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == dominant) {
                leftFreq++;
            }
            
            int rightFreq = totalFreq - leftFreq;
            int leftLen = i + 1;
            int rightLen = n - i - 1;
            
            // 检查两个子数组是否都有主导元素
            if (leftFreq * 2 > leftLen && rightFreq * 2 > rightLen) {
                return i;
            }
        }
        
        return -1;
    }
}

var minimumIndex = function(nums) {
    const n = nums.length;
    
    // 找到主导元素
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    let dominant = 0, totalFreq = 0;
    for (const [num, count] of freq) {
        if (count * 2 > n) {
            dominant = num;
            totalFreq = count;
            break;
        }
    }
    
    // 检查每个分割点
    let leftFreq = 0;
    for (let i = 0; i < n - 1; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组长度，k 是不同元素的个数。在最坏情况下 k = n，所以空间复杂度为 O(n)。

相关题目