分析数组中出现次数大于 N/K 的数之前，先来看一道简单的题目。
1、找出数组中出现次数大于数组长度一半的数
分析：
1、在数组中一次同时删掉两个不同的元素，如果存在某个数出现次数大于数组长度的一半，那么即使每次都删，最后也会至少剩下 1 个（不可能存在两个候选人，因为不可能存在两个数都超过一半）；
2、第一个数字作为第一个士兵即候选人 candiate，守阵地；candiate = 1 记录候选人个数；遇到相同元素，count++; 遇到不相同元素，即为敌人，同归于尽，count- -；当遇到 count 为 0 的情况，又以新的 i 值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是出现次数超过数组长度一半的元素。再遍历一次，确定这个士兵的个数看是否大于数组一半即可。
public class FindMajority { // 找到出现次数超过数组一半的数：如果有，也只有一个 public static int findOverHalfNum(int[] arr){ if(arr == null || arr.length < 1){ return Integer.MIN_VALUE; } int candiate = 0; int count = 0; for(int i = 0; i < arr.length; i++){ if(candiate == 0){ // 还没有候选人，当前值直接设置为候选人 candiate = arr[i]; count++; }else if(arr[i] == candiate){ // 有候选人，并且当前数和候选人一致 count++; }else{ // 有候选人，但是当前数和候选人不一致 count--; } } // 最后剩下的候选人是可能出现次数超过数组总长度一半的数，但是还需要校验下 if(count != 0){ count = 0; for(int i = 0; i < arr.length; i++){ if(arr[i] == candiate){ count++; } } if(count > arr.length / 2){ return candiate; } } return Integer.MIN_VALUE; } }2、找出数组中出现次数大于数组长度 N/K 的数
分析：
1、一次删除 K 个不同的数，那么你 N 个数，最多能减 N/K次，所以大于 N / K 的数一定会剩下来；
2、给你 K ，最多有 K - 1 个数是大于 N / K 【比如 > N / 4 的最多只有 3 个】，所以保留 K - 1 个候选人即可；
步骤：
1、候选表 HashMap：key为（K - 1）个候选 candiate，value 为它们分别出现的次数;
2、遍历到 arr[i] 时，看 arr[i] 是否在候选人中，如果与某一个候选人相同，就把属于那个候选的点数统计加 1，如果与所有的候选都不相同，先看当前的候选是否选满了，候选表中的大小为 K - 1 个，就是满了；否则就是没有选满。
2.1、如果不满，则把 arr[i] 作为一个新的候选，属于它的点数初始化为 1； 2.2、如果已满，说明此时发现了 k 个不同的数，arr[i] 就是第 k 个。此时把每一个候选各自的点数全部减 1，表示每个候选“付出”一个自己的点数，当前数也不要。如果某些候选的点数在减 1 之后等于 0，则还需要把这些候选人从候选表中删除，候选又变为不满的状态。 在上述过程结束后，还需要再遍历一次，验证被选出来的所有候选有哪些出现次数真的大于 N / K。
public class FindMajority { /** * 找到数组中出现次数大于 N/K 的数：最多有 K - 1 个 */ public static ArrayList<Integer> findOverKTimes(int[] arr, int k){ if(arr == null || arr.length < k){ return null; } // 候选表：用HashMap记录最多K-1个出现次数大于N/K的数的情况 HashMap<Integer, Integer> candiates = new HashMap<>(); for(int i = 0; i < arr.length; i++){ // 当前数在候选表中,出现次数加1 if(candiates.containsKey(arr[i])){ candiates.put(arr[i], candiates.get(arr[i]) + 1); }else if(candiates.size() < k - 1){ // 当前数不在候选表中，并且候选表还没有满时，直接插入 candiates.put(arr[i], 1); }else{ // 当前数不在候选表中，并且候选表已经满了，则将所有候选者次数都减1，当前数也不要（因为当前数次数也为1） allCandiatesDeleteOne(candiates); } } ArrayList<Integer> list = new ArrayList<>(); // 还有候选人 if(!candiates.isEmpty()){ // 得到候选人的真实个数 HashMap<Integer, Integer> reals = getReals(arr, candiates); for(Map.Entry<Integer, Integer> set : reals.entrySet()){ if(set.getValue() > arr.length / k){ list.add(set.getKey()); } } } return list; } public static void allCandiatesDeleteOne(HashMap<Integer, Integer> candiates){ for(Map.Entry<Integer, Integer> candiate : candiates.entrySet()){ Integer count = candiate.getValue(); if(count == 1){ // 当前候选人出现的次数仅为1，则直接从候选表中删除 candiates.remove(candiate.getKey()); }else{ // 出现次数减1 candiates.put(candiate.getKey(), --count); } } } public static HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> candiates){ HashMap<Integer, Integer> res = new HashMap<>(); for(Map.Entry<Integer, Integer> set : candiates.entrySet()){ int candiate = set.getKey(); int count = 0; for(int i = 0; i < arr.length; i++){ if(arr[i] == candiate){ count++; } } res.put(candiate, count); } return res; } }