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]

/**

 * 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

};