博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：pcwl_Java 一起交流秋招面试经验。
1、找出数组中出现次数大于数组长度一半的数
2、找出数组中出现次数大于数组长度 N/K 的数
一个数组中出现次数大于数组长度一般的数显然最多只有一个。
题目：在数组中找到出现次数大于数组长度一半的数。要求：时间复杂的 O(N)，额外空间复杂度 O(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;
}
}
要求：时间复杂度为 O(NK)，额外空间复杂度为 O(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 个，就是满了；否则就是没有选满。
在上述过程结束后，还需要再遍历一次，验证被选出来的所有候选有哪些出现次数真的大于 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;
}
}