友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
373. 查找和最小的 K 对数字
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2, 以及一个整数 k。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
提示:
-
1 <= nums1.length, nums2.length <= 105 -
-109 <= nums1[i], nums2[i] <= 109 -
nums1和nums2均为 升序排列 -
1 <= k <= 104 -
k <= nums1.length * nums2.length
思路分析
使用优先队列，存放最小的 k 个组合，使用最大堆，遇到更小的和，就弹出堆顶，加入新组合。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-15 23:12:43
*/
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> pq = new PriorityQueue<>(k, (a, b) ->
Long.compare((long) b.getFirst() + b.getLast(), (long) a.getFirst() + a.getLast()));
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (pq.size() < k) {
pq.add(Arrays.asList(nums1[i], nums2[j]));
continue;
}
long sum = (long) nums1[i] + nums2[j];
List<Integer> head = pq.peek();
long headSum = (long) head.getFirst() + head.getLast();
if (sum < headSum) {
pq.poll();
pq.offer(Arrays.asList(nums1[i], nums2[j]));
} else {
break;
}
}
}
return new ArrayList<>(pq);
}