Medium

题目描述

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：nums = [3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：nums = [1,2]
输出：[1,2]

约束条件：

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

**进阶：**你能用线性时间复杂度和 O(1) 空间复杂度解决这个问题吗？

解题思路

解题思路

这道题要求找出所有出现超过 ⌊n/3⌋ 次的元素。关键观察是：最多只能有2个这样的元素。

为什么？假设有3个或更多元素都出现超过 ⌊n/3⌋ 次，那么总出现次数会超过 3 × ⌊n/3⌋ ≥ n，这是不可能的。

方法一：哈希表统计（推荐理解）

遍历数组统计每个元素出现次数，然后找出超过 ⌊n/3⌋ 的元素。时间复杂度 O(n)，空间复杂度 O(n)。

方法二：Boyer-Moore 投票算法（最优解）

基于最多只有2个候选元素的事实，使用修改版的Boyer-Moore算法：

  1. 维护两个候选元素和对应计数器
  2. 第一轮：找出两个可能的候选元素
  3. 第二轮：验证候选元素是否真的超过 ⌊n/3⌋

算法核心：当遇到新元素时，如果与候选元素相同则计数+1，否则计数-1。当计数归零时更换候选元素。

这种方法时间复杂度 O(n)，空间复杂度 O(1)，满足进阶要求。

代码实现

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // 第一轮：找出两个候选元素
        for (int num : nums) {
            if (count1 > 0 && num == candidate1) {
                count1++;
            } else if (count2 > 0 && num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        // 第二轮：验证候选元素
        count1 = count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }
        
        vector<int> result;
        if (count1 > nums.size() / 3) result.push_back(candidate1);
        if (count2 > nums.size() / 3) result.push_back(candidate2);
        
        return result;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1, candidate2 = 0, 0
        count1, count2 = 0, 0
        
        # 第一轮：找出两个候选元素
        for num in nums:
            if count1 > 0 and num == candidate1:
                count1 += 1
            elif count2 > 0 and num == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1
        
        # 第二轮：验证候选元素
        count1 = count2 = 0
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
        
        result = []
        if count1 > len(nums) // 3:
            result.append(candidate1)
        if count2 > len(nums) // 3:
            result.append(candidate2)
        
        return result

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // 第一轮：找出两个候选元素
        foreach (int num in nums) {
            if (count1 > 0 && num == candidate1) {
                count1++;
            } else if (count2 > 0 && num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        // 第二轮：验证候选元素
        count1 = count2 = 0;
        foreach (int num in nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }
        
        List<int> result = new List<int>();
        if (count1 > nums.Length / 3) result.Add(candidate1);
        if (count2 > nums.Length / 3) result.Add(candidate2);
        
        return result;
    }
}

var majorityElement = function(nums) {
    let candidate1 = null, candidate2 = null;
    let count1 = 0, count2 = 0;
    
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        } else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    
    count1 = count2 = 0;
    for (let num of nums) {
        if (num === candidate1) count1++;
        else if (num === candidate2) count2++;
    }
    
    const result = [];
    const threshold = Math.floor(nums.length / 3);
    if (count1 > threshold) result.push(candidate1);
    if (count2 > threshold) result.push(candidate2);
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
Boyer-Moore 投票算法O(n)O(1)
哈希表统计O(n)O(n)

相关题目