面试题 17.14. 最小K个数

[案例需求]

TopK问题很普遍, 解题套路也很简单, 无非就是排序, 运用最基础的排序(如Array.sort(nums))复杂度为nlogn, 或者使用堆, 复杂度为nlogk,

或者在快排的基础上进行减治
详细参见此文: 点我

[思路分析一, 直接排序]

对原数组从小到大排序后取出前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;//或者直接拷贝也是可以的;//return Arrays.copyOfRange(nums, 0, k);}
}

[思路分析二, 使用堆]

我们使用一个大根堆实时维护数组的前k小值,
首先将前k个数插入到大根堆中, 随后从第k+1个数开始遍历,
如果当前遍历到的数比大根堆的堆顶的数要小, 就把堆顶的数弹出, 再插入到当前遍历到的数,
最后将大根堆的数存入到数组返回即可.

注意, 之所以使用大顶堆来维护最小的K个数是因为, 每次都是将新元素和堆顶(也就是这k个数中最大的数进行比较), 每次替换掉的都是这K个数中最大的数, 慢慢的等遍历完之后, 堆中K个数的最大, 较大, 次大…都被替换为了较小的数, 进而能够获得最小的K个数。

• (简单来说就是, 堆中K个数, 每次我清洗最大的数, 把他换成较小的数, 遍历完了整个序列后, 就获得了最小的K个数); 要想每次都能直接获得最大的数, 那肯定使用的是大顶堆咯;

[代码实现]

由于Java中优先队列是小根堆实现的, 所以我们要重新自定义比较器, 把数组排成单调递减的数;

class Solution {public int[] smallestK(int[] arr, int k) {int[] ans = new int[k];if(k == 0)return ans;//优先队列是小根堆实现的, 正好能够用来存储K的数, 比较合适替换后len - k 个数//单调递减, 小根堆//单调递增, 大根堆;PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer num1, Integer num2){return num2 - num1;}});//往堆中放入k个数for(int i = 0; i < k; i++){queue.offer(arr[i]);}//System.out.println(queue.peek());//比较len - k 个数和堆顶元素(queue.peek())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++){ans[i] = queue.poll();}return ans;//4. 随机选择, n}
}

[思路分析三, 随机选择(利用了快排思想, 但是减治)]

• 我们可以借鉴快排思想, 再快排中, 划分函数每次执行完之后会得到一个划分值partition, 这个值把数组分为了两个部分, 小于等于基准值pivot的元素都会被放到数组的左边, 大于的都会被放到数组的右边, 然后返回分界值的下标, 与快排不同的在于, 这里我们只处理划分的一边, 简单来说我们这种方法属于减治算法而不是快排的分治算法;

具体说明见前文(方法三, 随机选择) : 点我

我们定义函数 randomSelect(arr, left, right, k) 表示划分数组arr的[left, right]部分, 使得前k小 的数在数组的左侧, 在函数里我们调用快排的划分函数getPartition(), 假设划分函数返回的下标为partition(表示的是分界值(或基准值) 最终在数组中的位置), 即pivot是数组中第parition - left + 1 小的数, 那么会有这么三种情况:

1. 如果 partiton - left + 1 == k , 表示pivot就是第k小的数, 直接返回即可;
2. 如果 partition - left + 1 < k , 表示第k小的数在pivot的右侧, 因此递归调用randomSelect(arr, partition + 1, right, k - (partition - left + 1));
3. 如果 partition - left + 1 > k , 表示第k小的数在pivot的左侧, 递归调用randomSelect(arr, left, partition - 1, k);

函数递归入口为 randomized_selected(arr, 0, arr.length - 1, k)。在函数返回后，将前 k 个数放入答案数组返回即可。

[代码实现]

class Solution {public int[] smallestK(int[] arr, int k) {randomSelect(arr, 0, arr.length - 1, k);return Arrays.copyOfRange(arr, 0, k);}/**1. 根据划分函数确定基准值的位置partition;2. 如果partition - left + 1 == k, 那么返回left ==> partiton即可;3. 如果 partition - left + 1 > k, 问题缩小为左边界 left -> partition - 1;4. 如果partition - left + 1 < k, 前partition - left + 1 已经确定还需要去有边界确定 k - (partition - left + 1)*/public void randomSelect(int[] arr, int left, int right, int k){if(left < right){int partition = getRandomPartition(arr, left, right);int num = partition - left + 1;if(num == k){return;}else if(num > k){randomSelect(arr, left, partition - 1, k);}else{randomSelect(arr, partition + 1, right, k - (num));}}}public int getRandomPartition(int[] arr, int left, int right){int randomleft = new Random().nextInt(right - left + 1) + left;swap(arr, left, randomleft);return getPartition(arr, left, right);}public int getPartition(int[] arr, int left, int right){int pivot = arr[left];int tempLeft = left;while(left < right){while(left < right && arr[right] >= pivot)--right;while(left < right && arr[left] <= pivot)++left;swap(arr, left, right);}swap(arr, left, tempLeft);return left;}public void swap(int[] nums, int left, int right){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}
}

以上解法跟lt.215 基本相同, 仅在细微处做一些改变而已;

拓展: 自实现堆解决TopK问题;

可先参考前文: 堆排序的Java实现: 点我

这里先偷个懒把官解的代码贴上(写的是真烂, 无力吐槽), 以后尽快补上;

class Solution {public int findKthLargest(int[] nums, int k) {int heapSize = nums.length;buildMaxHeap(nums, heapSize);for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {swap(nums, 0, i);--heapSize;maxHeapify(nums, 0, heapSize);}return nums[0];}public void buildMaxHeap(int[] a, int heapSize) {for (int i = heapSize / 2; i >= 0; --i) {maxHeapify(a, i, heapSize);} }public void maxHeapify(int[] a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest]) {largest = l;} if (r < heapSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a, i, largest);maxHeapify(a, largest, heapSize);}}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}作者：LeetCode-Solution
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。