数组中找到出现次数大于N/K的数

说明

此题操作 Map 的时候，推荐使用 Entry 集合，尽量不要使用 map.get(), map.keySet() 等。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Created by Cser_W on 2017/10/19.
 */
public class PrintKMajor {

    public static void printKMajor(int[] arr,int k) {
        if (arr.length < 2)
            return ;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
           if (map.containsKey(arr[i])) {
               map.put(arr[i], map.get(arr[i]) + 1);
           } else {
               if (map.size() == k - 1) {
                   removeAllValueOne(map);
               } else {
                   map.put(arr[i], 1);
               }
           }
        }
        HashMap<Integer, Integer> map1 = countMap(map, arr);
        boolean flag = false;
        for (int key : map1.keySet()) {
            if (map1.get(key) > arr.length / k) {
                System.out.println(key);
                flag = true;
            }
        }
        System.out.println(flag ? "" : "no number");
    }

    public static void removeAllValueOne(Map<Integer, Integer> map) {
        if (map.size() < 1) {
            return ;
        }
        List<Integer> list = new LinkedList<>();
        for (int k : map.keySet()) {
            if (map.get(k) == 1) {
                list.add(k);
            }
            map.put(k, map.get(k) - 1);
        }
        for (int item : list) {
            map.remove(item);
        }
    }
    public static HashMap<Integer,Integer> countMap(Map<Integer, Integer> map, int[] arr) {
        HashMap<Integer,Integer> newMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                if (newMap.containsKey(arr[i])) {
                    newMap.put(arr[i],newMap.get(arr[i]) + 1);
                } else {
                    newMap.put(arr[i],1);
                }
            }
        }
        return newMap;
    }
    public static void main(String[] args){
        int[] arr = new int[]{1,2,2,2,2,3,4,5,6};
        printKMajor(arr,4);
    }
}