16、剑指 Offer 40. 最小的k个数
一、题目
剑指 Offer 40. 最小的k个数 难度简单
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
二、解法
2.1、排序（面试时也许会被直接 PASS ，不推荐使用）
核心思路
对原数组从小到大排序后取出前 k 个数即可。
复杂度分析
时间复杂度：O(n log n)，其中 n 是数组 arr 的长度，算法的时间复杂度即排序的时间复杂度。
空间复杂度：O(log n)，排序所需额外的空间复杂度为 O(log n)。
Code
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] result = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; ++i) {
result[i] = arr[i];
}
return result;
}
}
2.2、快速排序思想
核心思路
题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。
根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。
复杂度分析
时间复杂度：O(N)， 因为我们是要找下标为 k 的元素，第一次切分的时候需要遍历整个数组 (0 ~ n) 找到了下标是 j 的元素，假如 k 比 j 小的话，那么我们下次切分只要遍历数组 (0~k-1)的元素，反之如果 k 比 j 大的话，那下次切分只要遍历数组 (k+1～n) 的元素，总之可以看作每次调用 partition 遍历的元素数目都是上一次遍历的 1/2，因此时间复杂度是 N + N/2 + N/4 + … + N/N = 2N, 因此时间复杂度是 O(N)。
空间复杂度：O(log N)，划分函数的平均递归深度为 O(log N)。
Code
class Solution {
// 入口
public int[] getLeastNumbers(int[] arr, int k) {
// 边界条件
if (k >= arr.length) return arr;
// 递归调用
return quickSort(arr, k, 0, arr.length - 1);
}
// quick_sort() 的功能不是排序整个数组，而是搜索并返回最小的 k 个数.
private int[] quickSort(int[] arr, int k, int left, int right) {
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= arr[left]) j--;
while (i < j && arr[i] <= arr[left]) i++;
swap(arr, i, j);
}
swap(arr, i, left);
if (i > k) return quickSort(arr, k, left, i - 1);
if (i < k) return quickSort(arr, k, i + 1, right);
return Arrays.copyOf(arr, k);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
2.3、堆
核心思路
我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
复杂度分析
时间复杂度：时间复杂度：O(n log k)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 O(log k) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(n log k) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 k 个数。
Code
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
// 边界情况
if (k == 0) {
return new int[]{};
}
// 结果
int[] result = new int[k];
// 优先级队列
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
// 自定义比较器, 使之成为大顶堆. 默认为大顶堆
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
// 向优先队列中插入 arr 的前 k 个元素
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) {
result[i] = queue.poll();
}
return result;
}
}