05 August 2008
You are given two integer arrays nums1 and nums2 sorted in ascending 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.
Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.
Example 1:
1
2
3
4
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:
1
2
3
4
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:
1
2
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]
1) 暴力的想法是，维护一个大小为k的大顶堆把所有可能的结果加入堆即可，这没有利用到两个数组是有序的这一条件。
时间复杂度 O(m_n_logk)
2) 类似Ugly Number的做法，记录nums1[i]在nums2中当前的候选元素
时间复杂度O(k*len(nums1))
3) 利用小顶堆堆进一步优化上面方法
时间复杂度包括堆的初始化nlogn 和res的更新klogn 总O((k+n)longn)
暴力
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
27
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> result = new ArrayList<>();
k = Math.min(k, nums1.length * nums2.length); //注意k的取值
if (k == 0) {
return result;
}
Queue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> o2[0] + o2[1] - o1[0] - o1[1]);
for (int e1 : nums1)
for (int e2 : nums2) {
if (pq.size() < k) {
pq.offer(new int[]{e1, e2});
} else if (e1 + e2 <= pq.peek()[0] + pq.peek()[1]) {
pq.poll();
pq.offer(new int[]{e1, e2});
}
}
while (k-- > 0) {
int[] e = pq.poll();
result.add(0, Arrays.asList(e[0], e[1]));
}
return result;
}
}
记录一个数组的数在另一个数组位置的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> result = new ArrayList<>();
k = Math.min(k, nums1.length * nums2.length);
int[] ptrs = new int[nums1.length]; //ptrs[i]=j表示nums1[i]此时候选元素是nums2[j]
while (k-- > 0) {
int minIndex = -1, min = 0x7fffffff;
for (int i = 0; i < nums1.length; i++) { //在nums[i]的每个候选中挑选最小的【此处可以利用小顶堆快速找到，从而实现优化】
if (ptrs[i] < nums2.length && nums1[i] + nums2[ptrs[i]] < min) {
minIndex = i;
min = nums1[i] + nums2[ptrs[i]];
}
}
result.add(Arrays.asList(nums1[minIndex], nums2[ptrs[minIndex]]));
ptrs[minIndex]++;
}
return result;
}
}
最小堆
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
27
28
29
30
31
32
33
34
35
class Node {
int v; //nums1的元素值
int idx; //v对应的在nums2中的候选值索引
public Node(int _v, int _idx) {
v = _v;
idx = _idx;
}
}
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<>();
k = Math.min(k, nums1.length * nums2.length);
if (k == 0) return res;
Queue<Node> pq = new PriorityQueue<>(nums1.length,
(o1, o2) -> o1.v + nums2[o1.idx] - o2.v - nums2[o2.idx]);
for (int i = 0; i < nums1.length; i++) {
pq.offer(new Node(nums1[i], 0));
}
while (k-- > 0) {
res.add(Arrays.asList(pq.peek().v, nums2[pq.peek().idx]));
pq.peek().idx++;
if (pq.peek().idx == nums2.length)
pq.poll();
else
pq.offer(pq.poll()); //因为pq.peek().idx更新了，需要把堆顶Node取出后再重新放入
}
return res;
}
}