題目描述:給定兩個升序陣列 nums1 和 nums2,找出和最小的 k 個配對 (u, v)(u 來自 nums1,v 來自 nums2)。
解題思路:用最小堆。初始化時,將所有 (nums1[i] + nums2[0], i, 0) 加入堆(固定 nums1 的每個元素配 nums2 的第一個)。每次彈出最小的 (sum, i, j),加入結果,並推入 (nums1[i] + nums2[j+1], i, j+1)(下一個配對)。這保證每次取最小和。
時間複雜度:O(k log k) — 堆中最多有 min(n1, k) 個初始元素,每次操作 O(log k),執行 k 次。
空間複雜度:O(k) — 堆的大小上限為 k。
1. Push (nums1[i] + nums2[0], i, 0) for all i in [0, min(n1, k)) 2. Repeat k times: a. Pop (sum, i, j) from min-heap b. Append [nums1[i], nums2[j]] to result c. If j+1 < n2: push (nums1[i] + nums2[j+1], i, j+1) 3. Return result
暴力生成所有配對 O(n1 × n2 log(n1 × n2)):生成所有 n1×n2 個配對,排序取前 k 個 — 正確但當 n 很大時記憶體和時間不可接受。
二分搜尋 O(k log(max_sum)):二分搜尋答案(第 k 小的和),計算有多少配對的和 ≤ mid — 可行但實作複雜。