和最小的 k 个数对
# 📃 题目描述
题目链接:
- 373. 查找和最小的 K 对数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 剑指 Offer II 061. 和最小的 k 个数对 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个以升序排列的整数数组 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]
# 🔔 解题思路
帮助理解:我们需要的其实是堆底部的数据,这道题我们的目标是较小的数字,大根堆的底部就是较小的数字,所以这题用大根堆。
用最大堆来存储这 k 个和最小的数对。逐一将 m×n 个数对添加到最大堆中。
- 当堆中的数对的数目小于 k 时,直接将数对添加到堆中
- 如果堆中已经有k个数对,那么先要比较待添加的数对之和及堆顶的数对之和(也是堆中最大的数对之和):
- 如果待添加的数对之和 >= 堆顶的数对之和,那么堆中的 k 个数对之和都小于或等于待添加的数对之和,因此待添加的数对可以忽略。
- 如果待添加的数对之和 < 堆顶的数对之和,那么删除堆顶的数对,并将待添加的数对添加到堆中,这样可以确保堆中存储的是和最小的k个数对。每次都是将待添加的数对与堆中和最大的数对进行比较,而这也是用最大堆的原因。
接下来考虑如何优化。题目给出的条件是输入的两个数组都是递增排序的,这个特性我们还没有用到。
如果从第1个数组中选出第 k+1 个数字和第2个数组中的某个数字组成数对 p,那么该数对之和一定不是和最小的 k 个数对中的一个,因为第 1 个数组中的前 k 个数字和第 2 个数组中的同一个数字组成的 k 个数对之和一定是小于数对 p 之和的。
因此,不管输入的数组nums1有多长,最多只需要考虑前 k 个数字。同理,不管输入的数组nums2有多长,最多也只需要考虑前 k 个数字。
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<>();
// 根据(u,v)的和构建大根堆
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(o1, o2) -> (o2[0] + o2[1] - o1[0] - o1[1])
);
for (int i = 0; i < Math.min(k, nums1.length); i ++) {
for (int j = 0; j < Math.min(k, nums2.length); j ++) {
if (maxHeap.size() < k) {
maxHeap.offer(new int[] {nums1[i], nums2[j]});
}
else {
if (nums1[i] + nums2[j] < maxHeap.peek()[0] + maxHeap.peek()[1]) {
maxHeap.poll();
maxHeap.offer(new int[] {nums1[i], nums2[j]});
}
}
}
}
while (!maxHeap.isEmpty()) {
int[] temp = maxHeap.poll();
res.add(Arrays.asList(temp[0], temp[1]));
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(k)。优先队列中最多只保存 k 个元素
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10