剑指 Offer 40. 最小的k个数文章来源地址https://uudwc.com/A/V6B8J
优先级队列
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
for(int num : arr){
pq.offer(num);
if(pq.size() > k) pq.poll();
}
return pq.stream().mapToInt(x -> x).toArray();
}
}
快速排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k == 0) return new int[0];
quickSort(arr, 0, arr.length - 1, k - 1);
return Arrays.copyOf(arr, k);
}
int quickSort(int[] arr, int l, int r, int k){
if(l >= r) return arr[k];
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while(i < j){
while(arr[++i] < x);
while(arr[--j] > x);
if(i < j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
if(k <= j) return quickSort(arr, l, j, k);
else return quickSort(arr, j + 1, r, k);
}
}
文章来源:https://uudwc.com/A/V6B8J