Closed congr closed 5 years ago
Heap used, but it is very slow.
class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> list = new ArrayList();
if (k == 0) return list;
if (nums1.length == 0 || nums2.length == 0) return list;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b) -> (b[0]+b[1]) - (a[0]+a[1]));
for (int i = 0; i<nums1.length; i++) {
for (int j = 0; j<nums2.length; j++) {
pq.add(new int[]{nums1[i], nums2[j]});
if (pq.size() > k) pq.remove();
}
}
while (!pq.isEmpty()) list.add(pq.remove());
return list;
}
}
https://leetcode.com/problems/find-k-pairs-with-smallest-sums/