剑指offer28-最小k个数

思路

• hashmap存储,当大于len/2,终止
• 更巧妙地思路是，用一个count记录当前值与前一个值是否相等，相等count++,不等count--，当count=0时，则令pre=当前值，由于大于一半，所以最后数p一定是目标值，否则为0，但是无法解决的是不存在超过一半的值，比如 1 3 2 2，最后pre=2,然后结果是0.可以通过再遍历一遍数组判断是否是这个值。

代码

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            int cnt = map.containsKey(array[i])?map.get(array[i]):0;
            cnt++;
            map.put(array[i],cnt);
            if(cnt>array.length/2){
                return array[i];
            }
        }
        return 0;
    }
}