最小K个数

阳光穿透心脏的1/2处 2023-10-10 15:13 74阅读 0赞

[14天阅读挑战赛][14]

**目录**

最小K个数

方法一

方法二

--------------------

## 最小K个数 ##

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

![157cb5229ee74237a6f754a27a71d834.png][]

### 方法一 ###

对原数组从小到大排序后取出前 k 个数

class Solution {
        public int[] smallestK(int[] arr, int k) {
            int[] vec = new int[k];
            Arrays.sort(arr);
            for (int i = 0; i < k; ++i) {
                vec[i] = arr[i];
            }
            return vec;
        }
    }

### 方法二 ###

用一个大根堆实时维护数组的前 k小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可

> 具体步骤
> 
> 1. 先使用arr中前k个元素创建大堆  
> 2. 然后使用arr中剩余元素依次与堆顶元素比较，如果小于堆顶元素，替换堆顶元素，即：删除堆顶，然后将arr\[i\]插入堆中  
> 3. 最后堆中的k个元素就是所需的前k个最小的元素，放到数组中返回

class InitCmp implements Comparator<Integer>{
        public int compare(Integer num1,Integer num2){
            return num2-num1;
        }
    }
    class Solution{
        public int[] smallestK(int[] arr, int k){
            if(k == 0){
                return new int[0];
            }
            int[] ret = new int[k];
            InitCmp initCmp = new InitCmp();
            PriorityQueue<Integer> p = new PriorityQueue<Integer>(k,initCmp);
            for (int i = 0; i < k; i++) {
        // 先使arr中前k个元素创建大堆
                p.offer(arr[i]);
            }
            for (int i = k; i < arr.length; i++) {
                if(arr[i] < p.peek()){
                    p.poll();
                    p.offer(arr[i]);
                }
            }
            for (int i = 0; i < k; i++) {
                ret[i] = p.poll();
            }
            return ret;
        }
    
    }

> 时间复杂度：O(nlog⁡k)，其中 n是数组 arr 的长度。由于大根堆实时维护前 k小值，所以插入删除都是 O(log⁡k)的时间复杂度，最坏情况下数组里 n个数都会插入，所以一共需要 O(nlog⁡k)
> 
> 空间复杂度：O(k)，因为大根堆里最多 k个数

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[157cb5229ee74237a6f754a27a71d834.png]: https://img-blog.csdnimg.cn/157cb5229ee74237a6f754a27a71d834.png