博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer,可加微信:pcwl_Java 一起交流秋招面试经验。
目 录:
1、找出数组中出现次数大于数组长度一半的数
2、找出数组中出现次数大于数组长度 N/K 的数
1、找出数组中出现次数大于数组长度一半的数
一个数组中出现次数大于数组长度一般的数显然最多只有一个。
题目:在数组中找到出现次数大于数组长度一半的数。要求:时间复杂的 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;
}
}
2、找出数组中出现次数大于数组长度 N/K 的数
要求:时间复杂度为 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 个,就是满了;否则就是没有选满。
- 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;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)