373. 查找和最小的 K 对数字
373. 查找和最小的 K 对数字
题目
You are given two integer arrays nums1
and nums2
sorted in non- decreasing order and an integer k
.
Define a pair (u, v)
which consists of one element from the first array and one element from the second array.
Return the k
pairs (u1, v1), (u2, v2), ..., (uk, vk)
with the smallest sums.
Example 1:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
Constraints:
1 <= nums1.length, nums2.length <= 10^5
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1
andnums2
both are sorted in non-decreasing order.1 <= k <= 10^4
k <= nums1.length * nums2.length
题目大意
给定两个以 非递减顺序排列 的整数数组 nums1
和 nums2
, 以及一个整数 k
。
定义一对值 (u,v)
,其中第一个元素来自 nums1
,第二个元素来自 nums2
。
请找到和最小的 k
个数对 (u1,v1)
, (u2,v2)
... (uk,vk)
。
解题思路
可以通过优先队列(堆)来解决。我们可以维护一个小顶堆,堆中存储的是每一个可能的数对的和,同时记录这个数对在两个数组中的位置。每次弹出堆顶元素,并将下一个可能的数对入堆。最终返回的结果数组就是从小到大的前 k
个数对。
- 构建一个小顶堆,堆中的每个元素是一个三元组
(sum, i, j)
,其中sum
表示nums1[i] + nums2[j]
的和,i
和j
分别表示这个和在两个数组中的位置。 - 初始化堆中元素,将
(nums1[0] + nums2[0], 0, 0)
加入堆中。 - 重复以下步骤
k
次:- 弹出堆顶元素
(sum, i, j)
,将(nums1[i+1] + nums2[j], i+1, j)
和(nums1[i] + nums2[j+1], i, j+1)
分别加入堆中。注意要确保(i+1, j)
和(i, j+1)
没有超出数组范围。 - 将弹出的元素
(nums1[i], nums2[j])
加入结果数组。
- 弹出堆顶元素
复杂度分析
时间复杂度:
O(k log k)
- 初始堆的建立:这个步骤需要插入
k
个元素,每次插入的时间复杂度为O(log k)
,总的插入复杂度为O(k log k)
。 - 堆操作:从堆中弹出最小的和,弹出操作的时间复杂度为
O(log k)
。将新的数对加入到堆中,插入的时间复杂度也是O(log k)
。最多进行k
次弹出和插入操作,因此总的堆操作时间复杂度为O(k log k)
。
- 初始堆的建立:这个步骤需要插入
空间复杂度:
O(k)
,在堆中最多会同时存储k
个数对,因此堆的空间复杂度为O(k)
。
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number[][]}
*/
var kSmallestPairs = function (nums1, nums2, k) {
let heap = [];
const add = (val) => {
heap.push(val);
heapifyUp(heap.length - 1);
};
const pop = () => {
if (heap.length == 0) {
return null;
}
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
heapifyDown(0);
}
return top;
};
const heapifyUp = (i) => {
while (i) {
const parent = Math.floor((i - 1) / 2);
if (heap[i][0] < heap[parent][0]) {
[heap[i], heap[parent]] = [heap[parent], heap[i]];
i = parent;
} else {
break;
}
}
};
const heapifyDown = (i) => {
const left = i * 2 + 1;
const right = i * 2 + 2;
let min = i;
if (left < heap.length && heap[left][0] < heap[min][0]) {
min = left;
}
if (right < heap.length && heap[right][0] < heap[min][0]) {
min = right;
}
if (min !== i) {
[heap[i], heap[min]] = [heap[min], heap[i]];
heapifyDown(min);
}
};
let res = [];
if (!nums1 || !nums2 || nums1.length === 0 || nums2.length === 0 || k <= 0) {
return res;
}
for (let i = 0; i < Math.min(nums1.length, k); i++) {
add([nums1[i] + nums2[0], i, 0]);
}
while (k-- > 0 && heap.length > 0) {
const [sum, i, j] = pop();
res.push([nums1[i], nums2[j]]);
if (j + 1 < nums2.length) {
add([nums1[i] + nums2[j + 1], i, j + 1]);
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
378 | 有序矩阵中第 K 小的元素 | [✓] | 数组 二分查找 矩阵 2+ | |
719 | 找出第 K 小的数对距离 | 数组 双指针 二分查找 1+ | ||
2040 | 两个有序数组的第 K 小乘积 | 数组 二分查找 |