[数据结构与算法]面试题 17.14. 最小K个数

2021-09-03 LeetCode每日一题

链接：https://leetcode-cn.com/problems/smallest-k-lcci/

标签：数组、分治、快速选择、排序、堆

题目

设计一个算法，找出数组中最小的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))

分析

解法1：排序。

解法2：大顶堆。大顶堆就是根节点是最大的，左右子节点都比根节点小。正好可以用来求最小的k个数。初始化大顶堆容量为k，加入前k个数后，剩余的数加入时和堆顶元素比较，如果比堆顶元素小，则堆顶元素出堆，把这个数加入大顶堆重新排列，最后剩下的就是最小的k个数。从大到小排列。

Java自带的数据结构PriorityQueue默认是小顶堆，所以在初始化的时候需要指定排序函数。

解法3：小顶堆。根节点是最小的，不指定堆的容量，把数组的数全局放入堆中，取出前k个数即可。

注意PriorityQueue类的构造函数

PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator)
                     
IllegalArgumentException - 如果 initialCapacity小于1

而此题k是可能为0的。

编码

解法1：排序

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

        return res;
    }
}

解法2：大顶堆

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) {
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> {
            return b - a;
        });

        for (int num : arr) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (queue.peek() > num) {
                queue.poll();
                queue.offer(num);
            }
        }
        
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}

解法3：小顶堆

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) {
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);

        for (int num : arr) {
            queue.offer(num);
        }
        
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}