摩尔投票（绝对众数）

绝对众数：数组内出现次数大于 \(\lceil \cfrac{n}{2} \rceil\) 的数。

求绝对众数的方法：
暴力做法 \(O(n \log n)\) 排序并枚举左端点。

摩尔投票：\(O(n)\) 求出。

摩尔投票

丢个模板。

            int now = -1; int cnt = 0;
            f(j, 1, n) {
                if(x[j] != now) cnt--;
                else cnt++;
                if(cnt < 0) {
                    now = x[j]; cntx = 1;
                }
            }
            int ccnt = 0;
            f(j, 1, n) {
                if(x[j] == now) ccnt++;
            }
            if (ccnt >= len){
                cout << cnt << endl; 
            }   

注意，序列存在区间众数时，一定是 \(cnt\)。序列不存在区间众数时，\(cnt\) 随机。所以还要再扫一遍。

拓展到 n / k

https://leetcode.cn/problems/majority-element-ii/

可以证明，出现次数超过 \(n/k\) 的数最多只有 \(k - 1\) 个。否则必然违背「数总共只有 \(n\) 个」或者「当前统计的是出现次数超过 \(n / k\) 的数」的前提条件。

当明确了符合要求的数的数量之后，我们可以使用有限变量来代表这 \(k−1\) 个候选数及其出现次数。

然后使用「摩尔投票」的标准做法，在遍历数组时同时 check 这 \(k - 1\) 个数，假设当前遍历到的元素为 \(x\)：

• 如果 \(x\) 本身是候选者的话，则对其出现次数加一；
• 如果 \(x\) 本身不是候选者，检查是否有候选者的出现次数为 \(0\)：
  若有，则让 \(x\) 代替其成为候选者，并记录出现次数为 \(1\)；
  若无，则让所有候选者的出现次数减一。
  当处理完整个数组后，这 \(k - 1\) 个数可能会被填满，但不一定都是符合出现次数超过 \(n / k\) 要求的。

需要进行二次遍历，来确定候选者是否符合要求，将符合要求的数加到答案。

上述做法正确性的关键是：若存在出现次数超过 \(n / k\) 的数，最后必然会成为这 \(k - 1\) 个候选者之一。

我们可以通过「反证法」来进行证明：若出现次数超过 \(n / k\) 的数 \(x\) 最终没有成为候选者。

有两种可能会导致这个结果：

数值 \(x\) 从来没成为过候选者：

如果 \(x\) 从来没成为过候选者，那么在遍历 \(x\) 的过程中，必然有 \(k - 1\) 个候选者被减了超过 \(n / k\) 次，假设当前 \(x\) 出现次数为 \(C\)，已知 \(C>n/k\)，此时总个数为

\((k - 1) * C + C = C * k\)

再根据 \(C > n / k\)，可知 \(C * k > n\)，而我们总共就只有 \(n\) 个数，因此该情况恒不成立。

数值 \(x\) 成为过候选者，但被逐出替换了：

同理，被逐出替换，说明发生了对 \(x\) 出现次数减一的动作（减到 \(0\)），每次的减一操作，意味着有其余的 \(k - 2\) 个候选者的出现次数也发生了减一动作，加上本身被遍历到的当前数 \(num[i]\)，共有 \(k - 1\) 个数字的和 \(x\) 被一同统计。
因此，根据我们摩尔投票的处理过程，如果 \(x\) 成为过候选者，并被逐出替换，那么同样能够推导出我们存在超过 \(n\) 个数。

综上，如果存在出现次数超过 \(n / k\) 的数，其必然会成为 \(k−1\) 个候选者之一。