【搞定算法】找出数组中出现次数大于数组长度一半和 N/K 的数

深碍√TFBOYSˉ_ 2021-11-23 00:48 206阅读 0赞

博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java**  一起交流秋招面试经验。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

### **目 录**： ###

**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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190902171750658.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2,size_16,color_FFFFFF,t_70