📃 题目描述

题目链接：

• 373. 查找和最小的 K 对数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 剑指 Offer II 061. 和最小的 k 个数对 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
    [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

🔔 解题思路

帮助理解：我们需要的其实是堆底部的数据，这道题我们的目标是较小的数字，大根堆的底部就是较小的数字，所以这题用大根堆。

用最大堆来存储这 k 个和最小的数对。逐一将 m×n 个数对添加到最大堆中。

• 当堆中的数对的数目小于 k 时，直接将数对添加到堆中
• 如果堆中已经有k个数对，那么先要比较待添加的数对之和及堆顶的数对之和（也是堆中最大的数对之和）：
  • 如果待添加的数对之和 >= 堆顶的数对之和，那么堆中的 k 个数对之和都小于或等于待添加的数对之和，因此待添加的数对可以忽略。
  • 如果待添加的数对之和 < 堆顶的数对之和，那么删除堆顶的数对，并将待添加的数对添加到堆中，这样可以确保堆中存储的是和最小的k个数对。每次都是将待添加的数对与堆中和最大的数对进行比较，而这也是用最大堆的原因。

接下来考虑如何优化。题目给出的条件是输入的两个数组都是递增排序的，这个特性我们还没有用到。

如果从第1个数组中选出第 k+1 个数字和第2个数组中的某个数字组成数对 p，那么该数对之和一定不是和最小的 k 个数对中的一个，因为第 1 个数组中的前 k 个数字和第 2 个数组中的同一个数字组成的 k 个数对之和一定是小于数对 p 之和的。

因此，不管输入的数组nums1有多长，最多只需要考虑前 k 个数字。同理，不管输入的数组nums2有多长，最多也只需要考虑前 k 个数字。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();

        // 根据（u,v）的和构建大根堆
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (o1, o2) -> (o2[0] + o2[1] - o1[0] - o1[1])
        );

        for (int i = 0; i < Math.min(k, nums1.length); i ++) {
            for (int j = 0; j < Math.min(k, nums2.length); j ++) {
                if (maxHeap.size() < k) {
                    maxHeap.offer(new int[] {nums1[i], nums2[j]});
                }
                else {
                    if (nums1[i] + nums2[j] < maxHeap.peek()[0] + maxHeap.peek()[1]) {
                        maxHeap.poll();
                        maxHeap.offer(new int[] {nums1[i], nums2[j]});
                    }
                }
            }
        }

        while (!maxHeap.isEmpty()) {
            int[] temp = maxHeap.poll();
            res.add(Arrays.asList(temp[0], temp[1]));
        }


        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(k)。优先队列中最多只保存 k 个元素
• 时间复杂度：