leetcode 169 多数元素

题意简述

给定$n$个数，其中有某个数的出现次数大于$\lfloor \frac{n}{2} \rfloor$，求这个数。

算法分析

把这些数分成两个阵营，一个由每一个众数（即所求）组成，另一个由其他所有非众数组成。由题意知前一个阵营人数大于后一个。考虑维护一个候选众数$candidate$以及它出现的次数$count$，初始候选众数任意，出现次数为$0$。接下来扫描这$n$个数，如果被扫到的数$x$是当前候选众数，$count$加一，否则减一，如果$count$被减到$0$以下，将候选众数更新为$x$。最终的候选众数即为所求。

可以将整个过程想象为打擂台，和擂主（当前候选众数）相同的站到台上来，不同的干掉台上一个人，同归于尽。最坏的情况是非众数阵营内部没有发生同归于尽，同归于尽只发生在两个阵营之间，但即便如此众数阵营仍会因为数量多获胜。

此方法即摩尔投票。

代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};