数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

用HashMap实现

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length==0) return 0;
        if(array.length==1) return array[0];//只有一个元素的数组是容易代码遗漏的地方
        int key = array.length/2;
        int count;
        Map<Integer, Integer> visit = new HashMap<>();
        for(int i=0; i<array.length; i++){
            if(!visit.containsKey(array[i])){
                visit.put(array[i], 1);
            }else{
                count=visit.get(array[i]);
                if(count+1>key){
                    return array[i];
                }
                visit.remove(array[i]);
                visit.put(array[i], count+1);
            }
        }
        return 0;
    }