LeetCode 第229题：求众数 II

题目描述

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

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示

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

解题思路

对于这道题，简单的解法是使用哈希表计数，然后找出出现次数超过 ⌊ n/3 ⌋ 的元素。但题目进阶要求我们设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法。

我们可以使用**摩尔投票法（Boyer-Moore Voting Algorithm）**的扩展版本来解决这个问题。

方法：摩尔投票法

摩尔投票法通常用于找出数组中出现次数超过半数的元素（众数）。在这里，我们需要找出出现次数超过 ⌊ n/3 ⌋ 的元素，因此需要扩展这个算法。

关键思路：

1. 一个数组中，出现次数超过 ⌊ n/3 ⌋ 的元素最多只有两个（可以通过反证法证明）。
2. 我们使用两个候选值 candidate1、candidate2 和它们对应的计数器 count1、count2。
3. 遍历数组，对于每个元素，进行以下判断：
   • 如果等于 candidate1，则 count1++
   • 如果等于 candidate2，则 count2++
   • 如果 count1 为 0，则将当前元素设为新的 candidate1，count1 设为 1
   • 如果 count2 为 0，则将当前元素设为新的 candidate2，count2 设为 1
   • 如果都不满足，则 count1– 和 count2–
4. 最后，我们需要再次遍历数组，统计候选值的实际出现次数，确认它们是否超过 ⌊ n/3 ⌋。

时间复杂度：O(n)，其中 n 是数组的长度，需要遍历数组两次。 空间复杂度：O(1)，只使用了常数额外空间。

代码实现

C# 实现

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 (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 = 0;
        count2 = 0;
        
        // 第二次遍历：确认候选值的实际出现次数
        foreach (int num in nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        // 结果列表
        List<int> result = new List<int>();
        
        // 确认是否超过 ⌊ n/3 ⌋
        int threshold = nums.Length / 3;
        if (count1 > threshold) {
            result.Add(candidate1);
        }
        if (count2 > threshold) {
            result.Add(candidate2);
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 初始化候选值和计数器
        candidate1, candidate2 = 0, 1  # 选择不同的初始值避免冲突
        count1, count2 = 0, 0
        
        # 第一次遍历：找到可能的候选值
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif 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 = []
        
        # 确认是否超过 ⌊ n/3 ⌋
        threshold = len(nums) // 3
        if count1 > threshold:
            result.append(candidate1)
        if count2 > threshold:
            result.append(candidate2)
            
        return result

C++ 实现

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        // 初始化候选值和计数器
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // 第一次遍历：找到可能的候选值
        for (int num : 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 (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        // 结果向量
        vector<int> result;
        
        // 确认是否超过 ⌊ n/3 ⌋
        int threshold = nums.size() / 3;
        if (count1 > threshold) {
            result.push_back(candidate1);
        }
        if (count2 > threshold) {
            result.push_back(candidate2);
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	说明
C#	152 ms	45.2 MB	使用摩尔投票法实现，高效简洁
Python	112 ms	16.1 MB	Python的列表操作效率较高
C++	12 ms	15.8 MB	性能最优，内存消耗适中

补充说明

代码亮点

1. 使用摩尔投票法高效解决问题，避免了哈希表存储的空间开销
2. 通过两次遍历确保结果的正确性
3. 代码结构清晰，逻辑易于理解

优化方向

1. 在第一次遍历后，若两个候选值相同，可以直接合并计数器
2. 可以使用位运算优化部分比较操作，提高效率

解题难点

1. 理解摩尔投票法的扩展应用，从找一个众数扩展到找两个众数
2. 证明一个数组中出现次数超过 ⌊ n/3 ⌋ 的元素最多只有两个
3. 处理候选值相同的特殊情况（在Python实现中通过初始化不同的候选值避免）

常见错误

1. 忘记第二次遍历验证候选值的实际出现次数
2. 初始化两个相同的候选值可能导致结果重复
3. 数组为空时未正确处理

相关题目

• LeetCode 169. 多数元素 - 寻找出现次数超过 ⌊ n/2 ⌋ 的元素
• LeetCode 1150. 检查一个数是否在数组中占绝大多数 - 判断一个数在数组中是否出现超过半数