摩尔投票法一般情形下的证明
这里给出摩尔投票法正确性的证明，之前在网上看的资料都是以实现或者解释为主，这里给出一般情形下的证明。
参考资料：
摩尔投票法证明
描述
问题：
- 给定一个大小为$n$的整数数组，找出其中所有出现超过$\lfloor n/k \rfloor$次的元素。
可以用摩尔投票法在$O(k n)$时间复杂度，$O(k)$空间复杂度解法上述问题，算法接口：
- 算法名称：majorityKElement
- 输入：数组$a$，数组长度$n$，参数$k \ge 2$
- 输出：所有出现超过$\lfloor n/k \rfloor$次的元素
代码如下：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
return majorityKElement(nums, 3);
}
vector<int> majorityKElement(vector<int>& nums, int k){
vector<int> tmp(k - 1, nums[0]);
vector<int> cnt(k - 1, 0);
for (auto num : nums){
bool flag = true;
//先判断是否存在相等的元素
for (int i = 0; i < k - 1; i++){
if (num == tmp[i]){
flag = false;
//相等
cnt[i]++;
break;
}
}
//如果都不相等, 则判断是否存在有计数为0的元素
if (flag){
for (int i = 0; i < k - 1; i++){
if (num != tmp[i] && cnt[i] == 0){
flag = false;
cnt[i]++;
tmp[i] = num;
break;
}
}
}
//如果每个计数都大于0, 并且num和每个元素都不相等
if (flag){
for (int i = 0; i < k - 1; i++){
cnt[i]--;
}
}
}
//判断正确性
vector<int> res;
cnt = vector<int>(k - 1, 0);
for (int num : nums){
for (int i = 0; i < k - 1; i++){
if (num == tmp[i]){
cnt[i]++;
//保证不重复计数
break;
}
}
}
//生成结果
for (int i = 0; i < k - 1; i++){
if (cnt[i] > nums.size() / k){
res.push_back(tmp[i]);
}
}
return res;
}
};算法分为两个部分：
- 找出$k-1$个候选元素。
- 统计候选元素出现的次数是否大于$\lfloor n/ k\rfloor$。
下面将给出算法正确性的严谨证明。
证明
首先假设$k-1$个候选元素的$\text{cnt}$之和为$s$，然后假设
那么$\lfloor n/ k\rfloor = q$。
有如下两个结论：
- 最多只有$k-1$个元素出现个数大于$\lfloor n/ k\rfloor$
- 第一轮筛选后，出现次数大于$\lfloor n/ k\rfloor$的元素都出现在$k-1$个候选元素中。
结论1的证明：
如果有$k$个元素出现个数大于$\lfloor n/ k\rfloor $，那么这$k$个元素的次数总和
这就与元素的数量为$n$矛盾。
结论2的证明：
利用反证法，假设存在元素$a$，其出现次数为$l> \lfloor n/ k\rfloor $，并且没有出现在$k-1$个候选元素中。
显然我们有$l \ge \lfloor n/ k\rfloor+1 =q+1$
分为两种情形讨论：
- $a$从来没有成为候选元素。
- $a$成为过候选元素。
对于第一种情形，每次碰到$a$，$s$都要减去$k-1$（$k-1$个候选元素都减去$1$），所以$s$一共要减去$(k-1)l$，注意$s$最多增加$n -l$（对应于除$a$以外一共有$k-1$个元素，并且恰好分布在数组前$k-1$项中），所以$s$最后的值
但是根据算法，$s$在计算过程中必然非负，这就产生了矛盾。
对于第二种情形，假设$a$在候选元素中一共出现了$m$次（其中出现一次是指成为某个候选元素到其被替换），第$i$次出现在第$p_i$个位置，在该位置上$\text{cnt}[p_i]$一共增加了$c_i$次，那么由于最终$a$被替换，所以必然做了$c_i$次减法，这部分会让$s$减去$(k-1)c_i$；在$a$出现在候选元素最后一次后，还剩下$l-\sum_{i=1}^{m} c_i$个$a$，这部分会让$s$减去$(k-1)(l-\sum_{i=1}^m c_i)$。
注意$a$贡献的加法总和最多为$\sum_{i=1}^{m} c_i $，其余元素贡献的加法总和最多为$n-l$个剩余元素再减去对$a$贡献的减法$\sum_{i=1}^{k-1} c_i$，即
所以$s$最后的值
但是根据算法，$s$在计算过程中必然非负，这就产生了矛盾。