169. 多数元素

1 题解

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

2 思路

这个题目是个简单题，但是需要做到O(n)的时间复杂度需要用点技巧。

Boyer-Moore 投票算法

该算法用于在一串数中选出出现次数超过一半的数（众数），代码中使用ans表示“候选数”,使用count表示当前票数，初始时候选数是第一个数，票数为1。

1. ​投票机制​：
   • 每个元素都会对候选元素进行投票，如果相同则支持，如果不同则反对。
   • 代码中表现为count++
2. ​抵消机制​：
   • 当反对票多于支持票时，当前候选元素被淘汰，更新为新的候选元素。
   • 代码中表现为 count==-1时，候选数更新为当前的数，count=1
3. ​最终结果​：
   • 由于众数的数量超过一半，最终剩下的候选元素一定是众数。