寻找数组中的众数- 摩尔投票法

问题：在长度为n的数组中找出重复次数超过n/2的数（假设一定存在）。

存在O(n)的时间复杂度和O(1)的空间复杂度的解法，即摩尔投票法

摩尔投票法

摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。

JAVA代码

    public int majorityElement(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int moore = 0;
        int count = 0;
        
        for(int i = 0; i < nums.length; i++) {
            if(count == 0) {
                moore = nums[i];
            }
            if(nums[i] == moore) {
                count++;
            } else {
                count--;
            }
        }
        return moore;
    }

如果这个众数不一定存在的话，需要进行二次遍历判断。

类似的问题： 在长度为n的数组中找出重复次数超过n/3的数（不一定存在）。

同样的思路，使用两个虚拟数组，每次删除三个不同的数，最终虚拟数组中的两个数就是可能的答案，此时再遍历一遍数组，做一个验证即可。

#include<stdio.h>
#define LEN 8
int main(){
    int a[] = {1,2,1,2,3,3,1,2};
    int x, y, cx = 0, cy = 0;//两个虚拟数组
    for(int i = 0; i < LEN; ++i){
        if(x == a[i]) ++cx;
        else if(y == a[i]) ++cy;
        else if(cx == 0) x = a[i], cx = 1;
        else if(cy == 0) y = a[i], cy = 1;//这两个判断不能提前，因为可能把x,y赋为同一个值
        else --cx, --cy;
    }
    cx = 0,cy = 0;
    for(int i = 0; i < LEN; ++i){//锁定候选目标，遍历数组，计数，做验证
        if(a[i] == x) ++cx;
        else if(a[i] == y) ++cy;
    }
    if(cx > LEN/3){
        printf("超过1/3的数有：%d\n",x);
    }
    if(cy > LEN/3){
        printf("超过1/3的数有：%d\n",y);
    }
    return 0;
}