摘要：题目要求两个单调递增的整数数组，现分别从数组和数组中取一个数字构成数对，求找到个和最小的数对。思路这题采用最大堆作为辅助的数据结构能够完美的解决我们的问题。每从堆中取走一个数对，就插入，从而确保堆中的数对都可以从小到大遍历到。
题目要求
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[t]大。因此在优先队列中，我们存储所有的nums1中数字所能够构成的最小数对。每从堆中取走一个数对，就插入，从而确保堆中的数对都可以从小到大遍历到。
public List kSmallestPairs(int[] nums1, int[] nums2, int k) {
List result = new ArrayList();
if(nums1.length == 0 || nums2.length == 0 || k == 0) return result;
PriorityQueue heap = new PriorityQueue(new Comparator(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] + o1[1] - o2[0] - o2[1];
}});
for(int i = 0 ; i
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72557.html
