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: Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] 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: Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] 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: Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence:
[1,3],[2,3]
题目的意思很简单，给定两个升序排列的数组，从两个数组中各取一个元素进行配对，并对配对的两个进行求和，找出前K小的配对组合。
最直接的办法就是穷举，把所有的组合都列出来，得到最后的结果，这样的时间复杂度是N^2。那么有没有更简单的方法呢？
由于数组是有序的，那么最小的一个配对组合肯定是 [nums1[0],nums2[0] ]，并且 [nums1[i],nums2[j] ] 一定小于 [nums1[i],nums2[j+1] ]。知道这个规律后，次小的配对组合一定是在 [nums1[0],nums2[1] ] ...[nums1[i-1],nums2[0] ]， [nums1[i],nums2[0] ]之间产生。假设次小的值是 [nums1[i-1],nums2[0] ]，那么第三小的值就是在 [nums1[0],nums2[1] ] ...[nums1[i-1],nums2[1] ]， [nums1[i],nums2[0] ]。
所以，我们只需要再维护一个数组A，数组中下标对应nums1的下标，数组对应的值对应nums2的下标。每次只需要循环数组A,计算 nums[X] + nums[A[X]]，得到其中的最小值nums[X] + nums[A[X]]就是当前最小配对。找到最小配对后把数组A的A[x] 的值 +1，继续循环，直到找到第K个配对元素为止。
下面是参考代码:
/**
* Created by Administrator on 2016/7/25.
*/
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number[][]}
*/
var kSmallestPairs = function(nums1, nums2, k) {
if (nums1.length == 0 || nums2.length == 0){
return []
}
var count = 0;
var list = [];
for (var i = 0;i<nums1.length;i++){
list.push(0)
} var result = []
result.push([nums1[0],nums2[0]])
list[0] = 1
while( k > result.length && result.length < nums1.length*nums2.length){
//console.log(k,result.length)
var minIndex = 0;
var minSum = 0;
var j = 0;
for(j = 0;j<list.length;j++){
if (list[j] < nums2.length){
break
}
}
minSum = nums1[j] + nums2[list[j]]
for(var i = 0;i<list.length;i++){
if(minSum >= nums1[i] + nums2[list[i]]){
minIndex = i
minSum = nums1[i] + nums2[list[i]]
}
}
//console.log(minIndex)
result.push([nums1[minIndex],nums2[list[minIndex]]])
list[minIndex] ++;
}
return result };