【LeetCode】剑指 Offer 40. 最小的k个数
一、笨比解法
选择排序变形
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int [k];
for(int i = 0; i < k; i++){
int minIndex = i;
for(int j = i; j < arr.length; j++){
if(arr[minIndex] > arr[j]){
int temp = arr[minIndex];
arr[minIndex] = arr[j];
arr[j] = temp;
}
}
res[i] = arr[minIndex];
}
return res;
}
}
- 时间复杂度为 O(k * n)：k 为需要找的最小数的个数，n 为数组长度
- 空间复杂度为 O(k)：使用了大小为 k 的数组
二、堆排序
比较直观的想法是使用堆结数据结构来辅助的到最小的 k 个数。堆的性质是每次可以找出最大或最小的元素。我们可以使用一个大小为 k 的最大堆（大顶堆），将数组中的元素依次入堆，当堆的大小超过 k 时，便将多出的元素从堆顶弹出。我们以数组 [5,4,1,3,6,2,9]，k = 3 为例展示元素入堆的过程，如下面动图所示：
这样，由于每次从堆顶弹出的数据都是堆中最大的，最小的 k 个元素一定会留在堆里。这样，把数组中的元素全部入堆之后，堆中剩下的 k 个元素就是最大的 k 个数了
注意在动画中，我们并没有画出堆的内部结构，因为这部分内容并不重要。我们只需要直到堆每次会弹出最大的元素即可。在写代码的时候，我们使用的也是库函数中的优先队列数据结构，如 Java 中的 PriorityQueue，若想实现堆的结构，请参考【Java数据结构与算法】第十一章
class Solution{
public int[] getLeastNumbers(int[] arr, int k){
if(k == 0) return new int[0];
if(arr.length <= k) return arr;
Queue<Integer> heap = new PriorityQueue<>(k,(i1,i2) -> Integer.compare(i2,i1));
for(int i : arr){
if(heap.size() == 0 || heap.size() < k || i < heap.peek()){
heap.offer(i);
}
if(heap.size() > k){
heap.poll();
}
}
int[] res = new int[k];
int i = 0;
for(int j : heap){
res[i++] = j;
}
return res;
}
}
- 时间复杂度为 O(nlogk)，每个元素都需要进行一次入堆操作，入堆出堆的时间复杂度为 O(logk)
- 空间复杂度为 O(k)，使用了一个大小为 k 的堆
三、快速选择
题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为最小的 k 个数和其他数两部分即可，而快速排序的哨兵划分可完成此目标
根据快速排序原理，如果某次哨兵划分后基准数正好是第 k + 1 小的数字，那么此时基准数左边的所有数字便是题目所求的最小的 k 个数
根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k，若 true 则直接返回此时数组的前 k 个数字即可
getLeastNumbers() 函数：
- 若 k 大于数组长度，则直接返回整个数组
- 执行并返回 quick_sort() 即可，quick_sort() 的功能不是排序整个数组，而是搜索并返回最小的 k 个数
哨兵划分：
- 划分完毕后，基准数为 arr[i] ，左 / 右子数组区间分别为 [l,i-1]，[i+1,r]
递归或返回：
- 若 k < i，代表 k + 1 小的数字在左子数组中，则递归左子数组
- 若 k > i，代表 k + 1 小的数字在右子数组中，则递归右子数组
- 若 k = i，代表此时 arr[k] 即为第 k + 1 小的数字，则直接返回数组前 k 个数字即可
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k >= arr.length) return arr;
return quickSort(arr,0,arr.length-1,k);
}
private static int[] quickSort(int[] arr, int l, int r, int k) {
int i = l;
int j = r;
while(i < j){
while(i < j && arr[j] >= arr[l]) j--;
while(i < j && arr[i] <= arr[l]) i++;
swap(arr,i,j);
}
swap(arr,i,l);
if(i > k) quickSort(arr,l,i-1,k);
if(i < k) quickSort(arr,i+1,r,k);
return Arrays.copyOf(arr,k);
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
- 时间复杂度 O(n)，其中 n 为数组元素数量，对于长度为 N 的数组执行哨兵划分操作的时间复杂度为 O(n)。每轮哨兵划分后根据 k 和 i 的大小关系选择递归，由于 i 分布的随机性，则向下递归子数组的平均长度为 n/2。因此平均情况下哨兵划分操作一共有 2n - 1（等比数列求和），即总体时间复杂度为 O(n)
- 空间复杂度 O(logn)：划分函数的平均递归深度为 O(logN)