top-K问题
这类问题通常有两类解法,一种是使用优先队列(PriorityQueue),另一种是使用快排的partition
经典例题有:
面试题 17.14. 最小K个数
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] res = new int[k];
if(k == 0){
return res;
}
PriorityQueue<Integer> q =new PriorityQueue<>(((o1, o2) -> o2-o1));
for(int i:arr){
if(q.size() <k){
q.offer(i);
}else{
if(i<q.peek()){
q.poll();
q.offer(i);
}
}
}
int index = 0;
while(!q.isEmpty()){
res[index++] = q.poll();
}
return res;
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue=new PriorityQueue<>();
for(int i=0;i<nums.length;i++){
if(i<k){
queue.offer(nums[i]);
}else{
if(nums[i]>queue.peek()){
queue.poll();
queue.offer(nums[i]);
}
}
}
return queue.peek();
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
Map<Integer,Integer> map = new HashMap<>();
for(int i:nums){
int time = map.getOrDefault(i,0);
map.put(i,time+1);
}
PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->map.get(o1)-map.get(o2));
for(int i:map.keySet()){
if(q.size() < k){
q.offer(i);
}else{
if(map.get(i) > map.get(q.peek())){
q.poll();
q.offer(i);
}
}
}
int index = 0;
while(!q.isEmpty()){
res[index++] = q.poll();
}
return res;
}
}