本文主要是介绍373. Find K Pairs with Smallest Sums，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：输入两个整形升序数组，整数k，要求分别从2个数组中取出2个数组成对，输出和最小的k个对。
思路：1 参考leetcode discuss；
2 PriorityQueue实现最小堆，具体步骤如下：
初始化为array1中的前k个元素（注意，如果array1中的长度小于k，则为array1.length）和array2中的首个元素组成的pair；
每次从堆中剔除首个元素p（即目前堆中pair的和最小），然后将p中对应array2的下标后移（注意后移之前判断是否到达array2的边界），把<(int[2])p[0], p[1]=nums2[index+1]>添加到堆中。
时间复杂度为 O（klogk）。因为堆中的元素最多k个。
public class Solution {
class Pair{
int[] pair;
int idx; //numArry2[curIndex]
long sum;
public Pair(int idx, int n1, int n2) {
super();
this.idx = idx; //note current searched index of array2
pair = new int[]{n1, n2};
sum = (long)n1 + n2;
}
}
class ComPair implements Comparator{
public int compare(Pair o1, Pair o2) {
return Long.compare(o1.sum, o2.sum); //o1.sum - o2.sum
}
}
public ListkSmallestPairs(int[] nums1, int[] nums2, int k){
Listret = new ArrayList<>();
if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
return ret;
}
PriorityQueueq = new PriorityQueue<>(k, new ComPair());
for(int i = 0; i < nums1.length && i < k; i++){
q.offer(new Pair(0, nums1[i], nums2[0])); //klogk
}
for(int i = 0; i < k && !q.isEmpty(); i++){
Pair p = q.poll(); //remove head of the queue O(logk)
ret.add(p.pair);
if(p.idx < nums2.length-1){
q.offer(new Pair(p.idx+1, p.pair[0], nums2[p.idx+1]));
}
}
return ret;
}
}这篇关于373. Find K Pairs with Smallest Sums的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
