LeetCode169.多数元素

更新: 5/2/2026 字数: 0 字 时长: 0 分钟

题目链接：169. 多数元素

大意就是找出大于⌊ n/2 ⌋ 的元素，很好理解。暴力的思路很明确，即遍历，判断这个数字是否出现⌊ n/2 ⌋ 次，或者用hash表存储进行判断。

这里要求$O(1)$空间，我们使用投票法：

核心思路：多数元素的出现次数超过数组长度的一半，所以它和其他所有元素两两抵消之后，最后剩下的一定是多数元素。

比如：nums = [2,2,1,1,1,2,2]，多数元素是 2，出现了 4 次，其他元素一共出现 3 次。

即使每个 2 都和一个非 2 元素抵消，最后仍然至少会剩下一个 2。

所以我们可以维护两个变量num和count，分别代表当前候选元素以及他的票数。

如果count==0说明之前的变量已经被抵消完了，故需要选取当前元素作为新的变量。

如果num==nums[i]则count++，反之count--。最后剩下来的nums就是多数元素。

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0, num = 0;
        for(int i = 0;i < nums.size();i++) {
            if(count == 0) {
                num = nums[i];
            }
            if(num == nums[i])count++;
            else count--;
        }
        return num;
    }
};