数组中出现次数超过一半的数

• 哈希法：

  public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int len = array.length >> 1;
        Map<Integer, Integer> cntMap = new HashMap<>();
        for(int num : array){
            cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
        }
        for(int num : cntMap.keySet()){
            if(cntMap.get(num) > len)
                return num;
        }
        return 0;
    }
  }

  时间复杂度 O(N)
  空间复杂度 O(N)
  

• 候选法：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int target = -1;
        int cnt = 0;
        //找出出现次数最多的那个
        for(int i = 0; i < array.length; i++){
            if(cnt == 0){
                target = array[i];
                cnt++;
            }else{
                if(target == array[i])
                    cnt++;
                else cnt--;
            }
        }
        //检查是不是众数
        cnt = 0;
        for(int num : array){
            if(target == num) ++cnt;
        }
        if(cnt > (array.length >> 1)) return target;
        return 0;
    }
}

时间复杂度 O(1)
空间复杂度 O(N)