Find K Pairs with Smallest Sums

373. 查找和最小的K对数字

分析

初始化最小堆：
- 初始时，最小堆可以由 nums1[0] 和 nums2[i]（i 从 0 到 m-1）组成，因为 nums1 和 nums2 都是有序的，最小的数对总是以 nums1[0] 开头与 nums2 的元素组合
- 每个堆元素包含一个三元组 [sum, i, j]，其中 sum 是当前数对的和，i 是 nums1 的索引，j 是 nums2 的索引
使用堆来不断提取和最小的数对：
- 每次从堆中取出和最小的数对，并将其加入结果集。
- 如果 nums1[i+1] 和 nums2[j] 存在，推入堆中新的数对 nums1[i+1] 和 nums2[j] 的组合
堆的操作：
- 每次都取出和最小的数对进行处理，直到得到 k 个数对

时间复杂度

初始化堆：将 nums2 中的每个元素与 nums1[0] 配对，复杂度为 O(mlogm)，其中 m 是 nums2 的大小
每次弹出和插入操作的时间复杂度为 O(logk)

总体时间复杂度为 O(klogk)，其中 k 是要求的数对个数

空间复杂度

空间复杂度为 O(k)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k)
    {
        std::vector<std::vector<int>> res;   // 存储结果
        int n = nums1.size(), m = nums2.size();
        if (n == 0 || m == 0)                // 如果数组为空，直接返回空结果
            return res;

        // 使用优先队列（最小堆）存储 (sum, i, j)
        std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, std::greater<std::vector<int>>> heap;

        // 将 nums1[0] 与 nums2 中的每个元素配对，推入堆中
        for (int i = 0; i < m; ++i)
            heap.push({nums1[0] + nums2[i], 0, i});

        // 从堆中取出和最小的 k 对
        while (k-- && heap.size())
        {
            std::vector<int> t = heap.top();
            heap.pop();
            res.push_back({nums1[t[1]], nums2[t[2]]});  // 将结果加入 res

            // 如果 t[1]+1 < n，继续将 nums1[t[1]+1] 与 nums2[t[2]] 配对推入堆中
            if (t[1] + 1 < n)
                heap.push({nums1[t[1] + 1] + nums2[t[2]], t[1] + 1, t[2]});
        }
        return res;
    }
};