题目描述
思路：大顶堆+翻转
注意：该题有问题，代码可以通过测试用例。
方法一：
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<Node> heap = new PriorityQueue<>((e1, e2) -> e2.sum - e1.sum);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums1.length; i ++) {
for (int j = 0; j < nums2.length; j ++) {
heap.add(new Node(i, j, nums1[i] + nums2[j]));
if (heap.size() > k) {
heap.remove();
}
}
}
while (!heap.isEmpty()) {
Node node = heap.remove();
List<Integer> list = new ArrayList<>(Arrays.asList(nums1[node.i], nums2[node.j]));
res.add(list);
}
Collections.reverse(res);
return res;
}
class Node {
private int i;
private int j;
private int sum;
public Node(int i, int j, int sum) {
this.i = i;
this.j = j;
this.sum = sum;
}
}
}