Problem: 373. 查找和最小的 K 對數(shù)字

👨?🏫 參考題解

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {// 創(chuàng)建一個大小為 k 的結(jié)果列表，用于存儲和最小的 k 個數(shù)對List<List<Integer>> ans = new ArrayList<>(k); // 預(yù)分配空間// 創(chuàng)建一個優(yōu)先隊(duì)列（小根堆），存儲三元組 [nums1[i] + nums2[j], i, j]// 按照和 (nums1[i] + nums2[j]) 的大小升序排列PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 將 nums1 中前 k 個元素與 nums2 中第一個元素的和及其索引 i, j 加入到優(yōu)先隊(duì)列中for (int i = 0; i < Math.min(nums1.length, k); i++) { // 至多 k 個pq.add(new int[]{nums1[i] + nums2[0], i, 0});}// 循環(huán)直到找到 k 個數(shù)對或者優(yōu)先隊(duì)列為空while (ans.size() < k && !pq.isEmpty()) {// 取出堆頂元素，也就是當(dāng)前和最小的數(shù)對int[] p = pq.poll();int i = p[1]; // 取出 nums1 的索引int j = p[2]; // 取出 nums2 的索引// 將當(dāng)前和最小的數(shù)對加入結(jié)果列表ans.add(List.of(nums1[i], nums2[j]));// 如果 nums2 中還有剩余元素，將新的數(shù)對 [nums1[i], nums2[j + 1]] 放入優(yōu)先隊(duì)列if (j + 1 < nums2.length) {pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}}// 返回結(jié)果列表return ans;}
}