【牛客刷题】每日一练——最小K个数

✨hello，进来的小伙伴们，你们好耶！✨

🍅🍅系列专栏:【牛客刷题】

✈️✈️本篇内容: 最小K个数！

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

给大家推荐一个超级好用的刷题网站—牛客网！点击链接注册，开启刷题之路！

一、最小K个数

原题链接：最小K个数在线OJ

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

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

问题分析：这道题一上来大家肯定都会觉得非常简单，不就是数组中求前K个最小的元素嘛，直接数组排好序，然后循环打印出前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;
    }
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。

空间复杂度：O(logn)，排序所需额外的空间复杂度为 O(logn)。

方法二：

那么这一题的话就涉及到我们的数据结构中的Top-k问题（涉及到优先级队列的知识）

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

代码实现：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}

复杂度分析

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

空间复杂度：O(k)，因为大根堆里最多 k个数。