leetcode373.寻找和最小的k对数字

 这题优先想到小根堆，利用小根堆，存储一个三元组，三元组第一个数字表示选取两个数组的值的总和，用于小根堆排序，第二个数是数组1的下标，第三个数是数组2的下标

• 两个数组 nums1 和 nums2 都是 非递减排序 的，因此：

  • 最小的和一定是 nums1[0] + nums2[0]（两个数组的第一个元素）。
  • 次小的和可能是 nums1[0] + nums2[1] 或 nums1[1] + nums2[0]（在第一个元素的右侧或下一个元素中选择）。
  • 以此类推，每个数对 (i, j) 的右侧 (i, j+1) 和下侧 (i+1, j) 的数对和一定 不小于 当前和（因为数组非递减）。

• 因此，数对的和具有 局部有序性，可以通过 优先探索最小候选 的方式逐步扩展，而无需枚举所有数对。

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> result = new ArrayList<>();PriorityQueue<int[]> pq = new PriorityQueue<>(k, (arr1, arr2) -> arr1[0] - arr2[0]);for (int i = 0; i < nums1.length; i++) {pq.add(new int[]{nums1[i] + nums2[0], i, 0});}while (k-- > 0) {int[] poll = pq.poll();int i = poll[1];int j = poll[2];result.add(List.of(nums1[i], nums2[j]));if(j+1<nums2.length)pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}return result;}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> result = new ArrayList<>();int m = nums1.length;int n = nums2.length;if (m == 0 || n == 0 || k == 0) {return result;}// 最小堆，存储三元组 (sum, i, j)PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 初始化：将nums1的每个元素与nums2的第一个元素配对for (int i = 0; i < Math.min(m, k); i++) {minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});}// 提取k个最小的数对while (k > 0 && !minHeap.isEmpty()) {int[] current = minHeap.poll();int i = current[1];int j = current[2];result.add(Arrays.asList(nums1[i], nums2[j]));// 将下一个可能的候选加入堆if (j + 1 < n) {minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}k--;}return result;}
}