力扣 面试题 17.14. 最小K个数

题目来源：https://leetcode-cn.com/problems/smallest-k-lcci/

大致题意：
给定一个数组和整数 k，返回数组中前 k 小的数

思路

排序

直接使用快排。然后取出前 k 个元素。
时间复杂度 O(nlogn)，空间复杂度 O(logn)

优先队列

使用优先队列，也就是大根堆存下 k 个最小的数。

1.遍历数组。 初始时先放入 k 个数入队
2. 当已有 k 个数时，判断当前元素与队头元素，若当前元素小于队头元素则替换
3. 重复这个过程，直至遍历结束
4. 最后的队列中即为最小的 k 个数

代码：

public int[] smallestK(int[] arr, int k) {
        int[] ans = new int[k];
        // k 为 0，直接返回
        if (k == 0) {
            return ans;
        }
        // 定义大根堆
        PriorityQueue<Integer> kQueue = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int num : arr) {
            // 先放入 k 个数
            if (kQueue.size() < k) {
                kQueue.offer(num);
            }
            else {
                // 若更小则替换
                if (num < kQueue.peek()) {
                    kQueue.poll();
                    kQueue.offer(num);
                }
            }
        }
        // 出队，入数组
        for (int i = 0; i < k; i++) {
            ans[i] = kQueue.poll();
        }

        return ans;
    }