Problem: 面试题 17.14. 最小K个数
👩🏫 三叶题解
🍻 大根堆版
class Solution {public int[] smallestK(int[] arr, int k){PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);// 大根堆int[] ans = new int[k];if (k == 0)return ans;for (int x : arr){if (heap.size() >= k && x >= heap.peek())// 当前元素值大于堆顶元素值continue;if (heap.size() >= k)heap.poll();heap.add(x);}for (int i = k - 1; i >= 0; i--){ans[i] = heap.poll();}return ans;}
}
🍻 快速排序
class Solution {
// 快速选择int k;public int[] smallestK(int[] arr, int _k){k = _k;int n = arr.length;int[] ans = new int[k];qsort(arr, 0, n - 1);for(int i = 0; i < k; i++)ans[i] = arr[i];return ans;}private void qsort(int[] arr, int left, int right){if (left >= right)return;int l = left, r = right;int m = new Random().nextInt(right - left + 1) + left;// 随机选取标准值（划分点）下标swap(arr, m, left);// 把划分点放在当前区间的第一个位置
// 快速排序（划分区间）int x = arr[left];while (l < r){while (l < r && arr[r] >= x)// 找出右区间小于划分点的元素r--;while (l < r && arr[l] <= x)// 找出左区间大于划分点的元素l++;swap(arr, l, r);}swap(arr, l, left);// 把之前放在第一个位置的划分点放在中点上if (l > k)// 左区间超过 k 个元素，说明前 k 小肯定在左区间qsort(arr, left, l - 1);if (l < k)qsort(arr, l + 1, right);}/*** 交换数组左右下标的值* * @param arr 数组* @param l 左下标* @param r 右下标*/private void swap(int[] arr, int l, int r){int t = arr[l];arr[l] = arr[r];arr[r] = t;}}
🍻 快排免swap版
class Solution {public int[] smallestK(int[] arr, int k) {if(k == 0) return new int[]{};qselect(arr, 0, arr.length - 1, k - 1);return Arrays.copyOfRange(arr, 0, k);}public void qselect(int[] arr, int left, int right, int k) {if(left >= right) return;int pivot = pratition(arr, left, right);if(pivot == k){return;}else if (pivot < k){qselect(arr, pivot + 1, right, k);}else{qselect(arr, left, pivot - 1, k);}}// THU DSA 的快排模板，无需swappublic int pratition(int[] arr, int left, int right) {//首先备份我们的pivot，这里简单的选择第一个，如果需要避免最坏情况，前面可以shuffle一下int pivot = arr[left];//双指针左右靠拢while(left < right) {//先做右手边！因为我们备份了左指针当前的元素为pivot的，所以先搜索右边// qSort思路，比pivot大的全在pivot右手边，注意还有一个条件是要一直保证left < rightwhile(left < right && pivot <= arr[right]) {right --;}//退出上面的while循环是因为我们发现了pivot右边有比pivot小的//大胆交换，因为我们已经备份了第一个元素即pivot，下面左边同理arr[left] = arr[right];while(left < right && arr[left] <= pivot) {left ++;}arr[right] = arr[left];}//退出的条件是left == right，所以这个位置就是我们之前备份的pivot的位置，之后恢复好后返回下标即可arr[left] = pivot;return left;}
}
