hash

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        Map<Integer,Integer> hashMap=new HashMap<>();
        int len=numbers.length;
        for(int i=0;i<len;i++){
            hashMap.put(numbers[i],hashMap.getOrDefault(numbers[i],0)+1);
            if(hashMap.getOrDefault(numbers[i],0)>len/2){
                return numbers[i];
            }
        }
        return 0;
        
    }
}

候选法

加入数组中存在众数,那么众数一定大于数组的长度的一半。

思想就是:如果两个数不相等,就消去这两个数,最坏情况下,每次消去一个众数和一个非众数,那么如果存在众数,最后留下的数肯定是众数。

参考:https://blog.nowcoder.net/n/34901ad298694eacaa1a32da61a018be

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int len=numbers.length;
        int cond=-1;
        int count=0;
        for(int i=0;i<len;i++){
            if(count==0){
                cond=numbers[i];
                count++;
            }else{
                if(cond==numbers[i]){
                    count++;
                }else{
                    count--;
                }
            }


        }


        return cond;
    }
}