https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/
373. Find K Pairs with Smallest Sums
給你兩個有序陣列 nums1 和 nums2，任意 nums1 的元素和 nums2 的元素組合 (u, v) 為
一個 Pairs ，求出所有組合中總和最小的 k 個 Pairs。
Example 1:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
思路：
1.最簡單的方式就是用雙層迴圈把所有的組合放進一個Heap裡面並依照總和排序，但是
這樣時間複雜度是O(n^2*nlogn)，n > 100000 很明顯時間會爆掉。
2.我們可以一個一個的把Pair放入Heap，不必把 n^2 種結果都放進去，對於當前最小
Pair {nums[i], nums[j]} 來說，下一個最小的 Pair 必定只能是
{nums1[i], nums2[j + 1]} 或 {nums1[i + 1], nums2[j]} 兩者其一，前者對應了
拿下個右邊的元素，後者對應了拿下個左邊元素，我們可以先把左邊的所有元素與右
邊最小元素加入Heap，對應了所有的 {nums1[i + 1], nums2[j}，這樣每次我們都只要
放入 {nums1[i], nums2[j + 1]}，Heap每次取出來的值都會是最小。
3.另外為了避免 nums1 配對到重複的 nums2，我們還要額外用一個索引紀錄當前nums1[i]
已經匹配到右邊的哪些索引。
4.這樣時間複雜度就壓到O(Min(k, n1) * nlogn)，安全範圍 = =。
JavaCode：
---------------------------------------------------
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int
k) {
int n1 = nums1.length;
int n2 = nums2.length;
PriorityQueue<int[]> minHeap = new
PriorityQueue<>(Comparator.comparingInt(a -> (a[0] + a[1])));
for (int i = 0; i < Math.min(n1, k); i++) {
minHeap.add(new int[]{nums1[i], nums2[0], 0});
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
int[] curr = minHeap.poll();
res.add(Arrays.asList(curr[0], curr[1]));
int nums2Idx = curr[2];
if (nums2Idx < n2 - 1) {
minHeap.add(new int[]{curr[0], nums2[nums2Idx + 1],
nums2Idx + 1});
}
}
return res;
}
}
---------------------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1687890520.A.E91.html