🌕 剑指 Offer 40. 最小的k个数
2022年10月10日
- algorithm
🌕 剑指 Offer 40. 最小的k个数
难度: 🌕
问题描述
解法 1 - PriorityQueue
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
// 思路:
// 借助 优先队列
if(k == 0) {
return new int[0];
}
// k > 0
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
return b - a; // 创建 大根堆
}); // 默认小根堆
for(int i : arr) {
int size = queue.size();
if(size < k) {
queue.offer(i);
} else {
int peek = queue.peek();
if(peek > i) {
queue.poll();
queue.offer(i);
}
}
}
int[] res = new int[k];
for(int i = 0; i < k; i ++) {
res[i] = queue.poll();
}
// System.out.println(Arrays.toString(res));
return res;
}
}
输出 1
解法 2 - 变形快排
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
// 思路:
// 变形快排
if(k == 0) {
return new int[0];
}
mySol(arr, k, 0, arr.length - 1);
int[] res = new int[k];
for(int i = 0; i < k; i ++) {
res[i] = arr[i];
}
return res;
}
private void mySol(int[] arr, int k, int left, int right) {
// 递归终止条件
if(left >= right) {
return;
}
// left < right
int monitor = arr[left]; // 基准值,左边的都比它小,右边的都比它大
int i = left;
int j = right;
while(i < j) {
while(i < j && arr[j] >= monitor) {
j --;
}
while(i < j && arr[i] <= monitor) {
i ++;
}
swap(arr, i, j);
}
// 基准放到 i 处
swap(arr, left, i);
if(i == k - 1) {
return;
} else if(k - 1 > i) {
// 右边继续快排
mySol(arr, k, i + 1, right);
} else {
mySol(arr, k, left, i - 1);
}
}
private void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}