题目：力扣

解题思路：

可以先了解一下优先队列

对于集合中找前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;
    }
}