这道题可以有很多延伸:(1)简单的TopK算法 (2)大文件无法一次加载进内存如何找出TopK数字 (3)大文件找出频率次数最高的K个数字 (4)系统设计:Top-K Hitter找出一定时段内点击量最高的视频、博文
1)简单的TopK算法
优先队列实现
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] ans = new int[k];
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)-> o2-o1);
for(int i = 0; i < k; i++){
queue.offer(arr[i]);
}
for(int i = k; i < arr.length; i++){
// queue.offer(arr[i]);
// queue.poll();
if(queue.peek()>arr[i]){
queue.poll();
queue.offer(arr[i]);
}
}
for(int i=0; i<k; i++){
ans[i] = queue.poll();
}
return ans;
}
}
快速排序实现
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k >= arr.length) return arr;
return quickSort(arr, k, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int k, int l, int r) {
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
if (i > k) return quickSort(arr, k, l, i - 1);
if (i < k) return quickSort(arr, k, i + 1, r);
return Arrays.copyOf(arr, k);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
参考:
链接:https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solutions/1/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/
来源:力扣(LeetCode)