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;

    }
}

215. 数组中的第K个最大元素

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();
    }
}

347. 前 K 个高频元素

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;
    }
}