众数有关算法

背景

给定一个长度为n的数组的时候，找出其中的主元素，即该元素在数组中出现的次数大于n/2的取整。题目中已经假定所给的数组一定含有元素，且主元素一定存在。
题目来源

解决方案

1. 排序

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 nums.length/2的元素（下标从 0 开始）一定是众数。
排序可选择JAVA自带排序算法。

2.随机化

思路

因为超过n/2的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。

代码

 public int majorityElement(int[] nums) {
   
     int len=nums.length;
     while (true){
   
         Random random = new Random();
         int nextInt = random.nextInt(len);
         if(major(nums,nextInt)) return nums[nextInt];
     }

    }
    public boolean major(int[] nums ,int test){
   
        int ch=0;
        for(int i=0;i<nums.length;i++){
   
            if(nums[test]==nums[i]){
   
                ch++;
            }
        }
        if(ch>(nums.length/2)) return true;
        else return false;
    }

3.摩尔投票

思路

如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

代码

public int majorityElement(int[] nums) {
   
//摩尔投票
int vote=nums[0];
int count=1;
for(int i=1;i<nums.length;i++){
   
    if(count<1){
   
        vote=nums[i];
        count=0;
    }
    if(nums[i]==vote) count++;
    if(nums[i]!=vote) count--;
    

}
return vote;
    }