摩尔投票法是用来筛选出在长度为n数组中出现大于[n/2]次的元素数（[ ]取整符），俗名：寻找水王数。

因为非水王数出现次数一定会小于[n/2],因此水王数有且仅有1个。

对于这个问题，我们也可以用哈希表解决

#include <bits/stdc++.h>
using namespace std;
vector<int> majorityElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans;
    map<int, int> cnt;
    for (auto& v : nums) {
        cnt[v]++;
    }
    for (auto& v : cnt) {
        if (v.second > n / 2) {
            ans.push_back(v.first);
        }
    }
    return ans;
}
int main()
{
	int n;
	cin>>n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        nums.push_back(x);
    }
    for(auto& v : majorityElement(nums)){
        cout<<v<<" ";
    }
}

时间复杂度：O(n)，其中 n 为数组的长度。

空间复杂度：O(n)，其中 n 为数组的长度，使用哈希表需要开辟额外的空间。

但摩尔投票法时间复杂度：O(n)，其中 n 为数组的长度。空间复杂度：O(1)；

一、原理

第一种情况

在数组中每次删去两个不同的数，那么在最后剩下的数可能是水王数，那么我们再遍历一次数组，检查这个数出现次数是否大于[n/2]。

例1：[1,2,3,4,5] n=5

第一次删除1，2->[3,4,5]

第二次删除3，4->[5]

遍历发现[5]只出现一次，所以[5]不是水王数，那么[1,2,3,4,5]没有水王数。

例2：[2,2,3,2,4,2,2,6,2,3] n=10

第一次删2，3->[2,2,4,2,2,6,2,3]

第二次删2，4->[2,2,2,6,2,3]

第三次删2，6->[2,2,2,3]

第四次删2，3->[2,2]（无不同的数）

遍历发现[2]出现6次，所以[2]为[2,2,3,2,4,2,2,6,2,3]的水王数。

第二种情况

在数组中每次删除两个不同的数，最后没有剩下的数，那么这个数组没有水王数。

例：[1,2,3,4] n=4

第一次删1，2->[3,4]

第二次删3，4->[ ]

所以[1,2,3,4]没有水王数。

二、代码分析

对于数组，如何实现一次删除两个不同的数呢？

我们引入候选数cond以及票数hp，当hp=0时，我们认为没有候选数

(1)如果无候选，当前数成为候选，票数hp=1

(2)如果有候选

当前数 == 候选数，票数hp+1

当前数 != 候选数，票数hp-1

例1：[2,3,3,3,1,4,5,3,3,3,2] n=11 [3]出现6次

1)无候选数，候选sum=2，票数hp=1;

2)有候选数，当前数[3] !=候选数[2],hp-1->hp=0;

3)无候选数，候选sum=3，票数hp=1；

4)有候选数，当前数[3]==候选数[3],hp+1->hp=2;

5)有候选数，当前数[1]!=候选数[3],hp-1->hp=1;

…….

以此类推，直到数组最后一个数我们会得到候选数cond=3，票数hp=1;

之后我们先检查hp是否为0，如果为零，则说明没有水王数（原理的情况2），如果不为零，再检查候选数sum在数组出现的次数（原理的情况1）

三、代码表示

#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& nums) {
    int cond = 0;
    int hp = 0;
    for (auto& num : nums) {
        if(hp == 0){//无候选数
            cond=num;
            hp=1;
        }
        else if(num!=cond){//当前数与候选数不同
            hp--;
        }
        else {//当前数与候选数相同
            hp++;
        }
    }
    if(hp == 0){
        return -1;
    }
    hp = 0;
    for (auto& num : nums) {//判断候选数是否为水王数
        if(num==cond){
            hp++;
        }
    }
    return hp > nums.size()/2 ? cond : -1;
}
int main()
{
	int n;
	cin>>n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        nums.push_back(x);
    }
    cout<<majorityElement(nums)<<endl;
}

四、拓展

摩尔投票法是可以通过多线程来缩短时间的

比如有左右两个线程，然后比较左右线程的hp,hp大的候选数为水王数。

A.寻找分割点，使分割点两边的水王数相同，如力扣2780

#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& nums) {
    int cond = 0;
    int hp = 0;
    for (auto& num : nums) {
        if(hp == 0){//无候选数
            cond=num;
            hp=1;
        }
        else if(num!=cond){//当前数与候选数不同
            hp--;
        }
        else {//当前数与候选数相同
            hp++;
        }
    }
    if(hp == 0){
        return -1;
    }
    hp = 0;
    for (auto& num : nums) {//判断候选数是否为水王数
        if(num==cond){
            hp++;
        }
    }
    int n=nums.size();
    int lc = 0;//lc左侧水王数个数
    int rc = hp;//rc右侧水王数个数
    for(int i=0;i<n-1;i++){
        if(nums[i]==cond){
            lc++;
            rc--;
        }
        if(lc>(i+1)/2&&rc>(n-i-1)/2){
            return i;
        }
    }
    return -1;
}
int main()
{
	int n;
	cin>>n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        nums.push_back(x);
    }
    cout<<majorityElement(nums)<<endl;
}

B筛选出在长度为n数组中出现大于[n/k]次的元素数，如力扣229

这个时候我们先判断最多有多少个水王数，假设有k个水王数，那么k*水王数出现次数>n,矛盾

假设有k-1个水王数，(k-1)*水王数出现次数>n-n/k,存在可能性；

那么我们建立一个k-1* 2的二维数组

(1)候选数不足k-1个，

当前数==其中一个候选数，hp+1；

当前数!=任何一个候选数，当前数为候选数，hp=1；

(2)候选数达到k-1个

当前数==其中一个候选数，这该候选数hp+1

当前数!=任何一个候选数，所有候选数hp-1(相当于一下子删了k个不同的数）

最后遍历每个候选数出现次数，判断是否符合条件

例：[3,5,2,3,4,2,5,3,7,7,6] k=4 <候选数，票数>

1)候选数<k-1,候选集[<3,1>]

2)候选数<k-1,候选集[<3,1>,<5,1>]

3)候选数<k-1,候选集[<3,1>,<5,1>,<2,1>]

4)候选数==k-1,当前数==候选数[3]->候选集[<3,2>,<5,1>,<2,1>]

5)候选数==k-1,当前数[4]!=候选数[3]->候选集[<3,1>,<5,0>,<2,0>](注意hp=0时候选数

6）候选数<k-1，候选集[<3,1>,<2,1>]

…….

#include <bits/stdc++.h>
using namespace std;
void update(vector<vector<int>>& count, int k, int num) {
    for (int i = 0; i < k; i++) {
        if (count[i][0] == num && count[i][1] > 0) {//当前数等于候选数
            count[i][1]++;
            return;
        }
    }
    for (int i = 0; i < k; i++) {
        if (count[i][1] == 0) {//候选数<k-1
            count[i][0] = num;
            count[i][1]++;
            return;
        }
    }
    for (int i = 0; i < k; i++) {
        if (count[i][1] > 0) {//当前数不等于任何候选数，候选数票数-1
            count[i][1]--;
        }
    }
}
vector<int> majorityElement(vector<int>& nums,int k) {
    vector<vector<int>> count(--k, vector<int>(2, 0));
    for(auto& num : nums) {
        update(count, k, num);
    }
    vector<int> ans;
    for (auto& c : count) {
        if (c[1] > 0) {
            int num = c[0];
            int sum=0;
            for (auto& n : nums) {
                if (n == num) {
                    sum++;
                }
            }
            if (sum > nums.size() / (k+1)) {//在建立count时进行了--k
                
                ans.push_back(num);
            }
        }
    }
    return ans;
    
}
int main()
{
	int n,x;
	cin>>n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
        cin>>x;
        nums.push_back(x);
    }
    for (auto& i : majorityElement(nums, 3)) {
        cout << i << " ";
    }
}