Moore majority vote 算法

摩尔投票法基于这样一个事实：

当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。

我们采用一个虚拟数组（在实现中可以使用两个变量代替，一个代表当前数组内元素的个数，另一个储存当前的候选数）来储存候选的众数。当遇到相同的数的时候向虚拟数组中加入当前的候选数，遇到不同的数的时候从虚拟数组中删除一个候选数。如果虚拟数组大小为0，向虚拟数组中加入当前位置的数作为候选数。遍历完成后数组中剩余的元素就是众数。

因为众数大于数组的一半，哪怕最极端的其它数全都相同，众数也能在数组中剩余不少于2m-n（其中m为众数的数量，n为数组大小）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int majorityElement(vector<int>& nums) {
        int res=0,cnt=0;
        for(int i=0;i<nums.size();i++){
            if(cnt==0) {
                res=nums[i];
                cnt++;
            }
            else{
                res==nums[i]?cnt++:cnt--;
            }
        }
        return res;
    }



扩展


求在长度为n的数组中出现次数超过n/3的数

明显的，长度超过n/3的数最多只有2个。
按照摩尔投票法的思路，我们可以设置两个虚拟数组，最终两个数组中的数就是满足条件的数（如果题目没有说明一定存在，则可以进行一轮遍历验证）

如下方代码所示逻辑，相当于平均每次访问了3个数字，因为所求数字重复次数超过了n/3，所以按平均的情况每次访问时都会存在有所求数字保留在虚拟数组中，即：一定会占据虚拟数组一个栏位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getSuitableNumber(vector<int> arr) {
    int x, y, cx = 0, cy = 0;//两个虚拟数组
    x = 300000;//任意一个不存在于数组中的值作为初始值
    y = 400000;
    for (int i = 0; i < arr.size(); ++i) {
        if (x == arr[i]) ++cx;
        else if (y == arr[i]) ++cy;
        else if (cx == 0) x = arr[i], cx = 1;
        else if (cy == 0) y = arr[i], cy = 1;//这两个判断不能提前，因为可能把x,y赋为同一个值
        else --cx, --cy;
    }
    cx = 0, cy = 0;
    for (int i = 0; i < arr.size(); ++i) {//锁定候选目标，遍历数组，计数，做验证
        if (arr[i] == x) ++cx;
        else if (arr[i] == y) ++cy;
    }
    if (cx > arr.size() / 3) {
        printf("超过1/3的数有：%d\n", x);
    }
    if (cy > arr.size() / 3) {
        printf("超过1/3的数有：%d\n", y);
    }
}

长度为n的数组中出现次数超过n/k的数

按照之前的逻辑，只需设置k-1个虚拟数组，最后留下的数字即可能是满足条件的数。