最小的 k 个数
# 📃 题目描述
题目链接:剑指 Offer 40. 最小的k个数 (opens new window)
# 🔔 解题思路
# 最大堆
和 剑指 Offer II 060. 出现频率最高的 k 个数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 思路一样,本题用一个大小为 k 的大根堆,如果堆的元素个数 < k,那么直接插入,如果堆的元素个数 == k,并且当前遍历到的数 > 大根堆的堆顶,那么这个数一定不是最小的 k 的数
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) {
return new int[0];
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
(o1, o2) -> o2 - o1
);
for (int num : arr) {
if (maxHeap.size() < k) {
maxHeap.offer(num);
}
// maxHeap.size() >= k
else {
if (num >= maxHeap.peek()) {
continue;
}
maxHeap.poll();
maxHeap.offer(num);
}
}
int[] res = new int[k];
int i = 0;
while (!maxHeap.isEmpty()) {
res[i ++] = maxHeap.poll();
}
return res;
}
}
# 快速排序
快速排序 partition 的作用,返回 pivot 的最终位置,并且,左边的数都小于 arr[pivot],右边的数都大于 arr[pivot]
这道题不需要对最小的 k 个数进行排序,如果 pivot 的下标正好就是 k - 1,那么 arr[0, pivot]
就是 最小的 k 个数
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
select(arr, 0, arr.length - 1, k);
return Arrays.copyOf(arr, k);
// return Arrays.copyOfRange(arr, 0, k);
}
private void select(int[] arr, int left, int right, int k) {
if (left > right) {
return ;
}
int pivot = partition(arr, left, right);
// 找到 pivot == k -1, 则停止排序
if (pivot == k - 1) {
return ;
}
else if (pivot < k - 1) {
select(arr, pivot + 1, right, k);
}
else {
select(arr, left, pivot - 1, k);
}
}
private int partition(int[] arr, int left, int right) {
int index = left + new Random().nextInt(right - left + 1);
swap(arr, index, left);
int pivot = left;
while (left < right) {
while (left < right && arr[right] >= arr[pivot]) {
right --;
}
while (left < right && arr[left] <= arr[pivot]) {
left ++;
}
if (left < right) {
swap(arr, left, right);
}
}
swap(arr, left, pivot);
return left;
}
private void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10