无法播放?请 点击这里 跳转到Youtube
切换视频源:
题目链接: https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
GitHub答案源代码请点击这里
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
List<List<Integer>> res = new ArrayList<>();
if (m == 0 || n == 0) {
return res;
}
boolean[][] visited = new boolean[m][n];
PriorityQueue<Cell> heap = new PriorityQueue<>((a, b) -> (nums1[a.i] + nums2[a.j]) - (nums1[b.i] + nums2[b.j]));
heap.offer(new Cell(0, 0));
visited[0][0] = true;
while (k > 0 && !heap.isEmpty()) {
Cell top = heap.poll();
res.add(Arrays.asList(nums1[top.i], nums2[top.j]));
Cell nei = new Cell(top.i + 1, top.j);
if (nei.i < m && !visited[nei.i][nei.j]) {
visited[nei.i][nei.j] = true;
heap.offer(nei);
}
nei = new Cell(top.i, top.j + 1);
if (nei.j < n && !visited[nei.i][nei.j]) {
visited[nei.i][nei.j] = true;
heap.offer(nei);
}
k--;
}
return res;
}
}