373. 查找和最小的 K 對數字

思路

最初的點對一定是兩個列表的第一個元素配對，而第二對就需要比較兩種方案，選擇了之後就會有更多方案列入考量
不能將所有的點組合成列表後排序，那樣需要 $O(n^2)$ 的時間，會超時。

因為每次都需要從考量的方案中選出最優，而且每次考量的方案會變化，
面對這種資料會變動又需要求極值的題目，使用優先隊列。

使用優先隊列拿出成本最小的節點之後，比它高成本的有兩個選項,
nums1[i + 1] + nums2[j], nums1[i] + nums2[j + 1]這兩種，都需要放到堆裡
但這樣會導致(0, 1), (1, 0)拿出時, 都會加入(1, 1)的點

為了只加一次，統一規定只放 nums1[i] + nums2[j + 1]的點
也就是點 $(i, j)\to(i, j + 1)\to(i, j + 2)\to\dots$\

這樣在 pq 中延展出來的點都不會提高 i, 所以要在一開始就把所有可能的 i 加進去。
比如 $(3, 0)\to(3, 1)\to(3, 2)\to\dots$

程式碼

堆

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        using tiii = tuple<int, int, int>;
        int n = nums1.size(), m = nums2.size();
        priority_queue<tiii, vector<tiii>, greater<tiii>> pq; // nums1[i] + nums2[j], i, j

        for(int i = 0; i < min(n, k); i++) { // 最多只要 k 個點, 所以 pq 放更多點也沒有意義
            pq.emplace(nums1[i] + nums2[0], i, 0);
        }
        vector<vector<int>> res;
        while(k--) {
            auto [_, i, j] = pq.top();pq.pop();
            res.push_back({nums1[i], nums2[j]});
            if(j + 1 < m) {
                pq.emplace(nums1[i] + nums2[j + 1], i, j + 1);
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(k\log\min(n,k))$
• 空間複雜度：$O(\min(n+k))$，