查找和最小的K对数字 优先队列

题目：力扣

解题思路：

可以先了解一下优先队列

对于集合中找前K小的元素，常用的方法是可以使用大小为K的大根堆（用一个降序的优先队列实现），依次遍历集合中的元素

当堆未满时，即元素个数小于K

                直接将元素加入到堆里

当堆满了时

                若当前元素大于堆顶，则跳过

                若当前元素不大于堆顶，则将堆顶移除，在堆中加入当前元素

最后，堆里的元素就是前K小的元素。

class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<List<Integer>> queue = new PriorityQueue<>(k, (o1,o2)->{return (o2.get(0)+o2.get(1) - o1.get(0)-o1.get(1));}); for(int i = 0; i < Math.min(nums1.length, k); i++){ for(int j = 0; j < Math.min(nums2.length, k); j++){ if(queue.size() == k && (queue.peek().get(0)+ queue.peek().get(1) < nums1[i]+nums2[j]) ){ break; } //没有break表示当前的和小于最大的，若队列满了则把最大的出队，再加入当前的 if(queue.size() == k){ queue.poll(); } ArrayList<Integer> new_pair = new ArrayList<>(); new_pair.add(nums1[i]); new_pair.add(nums2[j]); queue.add(new_pair); } } List<List<Integer>> res = new LinkedList<>(); while(!queue.isEmpty()){ res.add(0, queue.poll()); } return res; } }