【一起来刷题java】——TOPK问题

[参考文献]((382条消息) 拜托，面试别再问我TopK了！！！_架构师之路-CSDN博客)

本文参考了上面的文章，并做了自我总结，希望会有所帮助。

topK问题：从很多个数中得到较大的K个元素。

我们固然可以建成一个大堆，然后弹出K次就可以找到前K个元素，但是建立一个N个元素的大根堆，再每次向下调整的时间复杂度是O(n*lgn)

所以，为了简化这个问题，就可以让N个数的前k个元素建立一个只有k个元素的小根堆，小根堆的堆顶就是最小的元素，

对于n-k个元素，如果哪个元素比堆顶的元素大，那么就pop堆顶元素，然后将该元素加入堆中

这样，遍历完成该操作后，留下来的就是前K个大的元素

这样的时间复杂度就是O(n*lgk)比上面的快了很多

其他结论：

堆顶的元素就是第K大的元素其他的非堆顶的元素就是先K个大的元素

代码实现：

class Solution {
    public int[] topK(int[] nums, int k) {
        PriorityQueue pq=new PriorityQueue<>();
        for(int i=0;ipq.peek()){
                    pq.poll();
                    pq.offer(nums[i]);
                }
            }
        }
        int[] ret=new int[k];
        for(int i=0;i 
查找和最小的K对数字 
[题目链接](373. 查找和最小的 K 对数字 - 力扣（LeetCode） (leetcode-cn.com))
 
上面的这道题和topK问题是差不多的，只是多了数对的问题。
 
使用了list而已
 
class Solution {
    public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue> priorQueue = new PriorityQueue<>(k, new Comparator>() {
            @Override
            public int compare(List o1, List o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        //注意要取K，和length的最小值，因为这个是一个升序数组，防止因length太大而陷入死循环
        for(int i=0;i list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    priorQueue.offer(list);
                }else{
                    int top=priorQueue.peek().get(0)+priorQueue.peek().get(1);
                    if(nums1[i]+nums2[j] list=new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        priorQueue.offer(list);
                    }
                }

            }
        }
        List> retlist=new ArrayList<>();
        int size=priorQueue.size();
        for(int i=0;i