题目要求
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.
两个单调递增的整数数组，现分别从数组 1 和数组 2 中取一个数字构成数对，求找到 k 个和最小的数对。
思路
这题采用最大堆作为辅助的数据结构能够完美的解决我们的问题。观察数组我们可以看到，从 nums1 中任意取一个数字，其和 nums2 中的数字组成的最小数对一定是 <nums1[k], nums2[0]>，同理，我们可以知道，<nums1[k], nums2[t+1]> 的值一定比 nums1[k], nums2[t] 大。因此在优先队列中，我们存储所有的 nums1 中数字所能够构成的最小数对。每从堆中取走一个数对 <nums1[k], nums2[t]>，就插入 <nums1[k], nums2[t+1]>，从而确保堆中的数对都可以从小到大遍历到。
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<int[]>();
if(nums1.length == 0 || nums2.length == 0 || k == 0) return result;
PriorityQueue<int[]> heap = new PriorityQueue<int[]>(new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] + o1[1] – o2[0] – o2[1];
}});
for(int i = 0 ; i<nums1.length ; i++){
heap.offer(new int[]{nums1[i], nums2[0], 0});
}
while(k– != 0 && !heap.isEmpty()) {
int[] min = heap.poll();
result.add(new int[]{min[0], min[1]});
if(min[2] == nums2.length) continue;
heap.offer(new int[]{min[0], nums2[min[2]+1], min[2] + 1});
}
return result;
}