[leetcode]373. Find K Pairs with Smallest Sums -- JavaScript代码-蒲公英云

[leetcode]373. Find K Pairs with Smallest Sums -- JavaScript代码

悠悠 2022-09-24 08:29 196阅读 0赞

先上代码，这段js代码执行的效率还是比较高的～

/** * @param {number[]} nums1 * @param {number[]} nums2 * @param {number} k * @return {number[][]} */
var kSmallestPairs = function(nums1, nums2, k) {
    var len1 = nums1.length;
    var len2 = nums2.length;
    var cnt = Math.min(k, len1*len2);  
    var index = [];// 长度为len1 全都初始化为0； 
    for(var i=0;i<len1;i++){
        index.push(0);
    }
    console.log(index);
    var ans = [];  
    while(cnt-- > 0)  
    {  
        var temMin = Infinity, m = 0;  
        for( i =0; i < len1; i++)  
            if(index[i] < len2 && nums1[i]+nums2[index[i]] < temMin)   
                temMin= nums1[i]+nums2[index[i]], m = i;  
        ans.push([nums1[m], nums2[index[m]++]]);  
    }  
    return ans;
};

思路：
由于题目给出的两个数组已经是从大到小排列好的，这条信息如果好好利用，是可以大大提高代码效率的。
算法首先：为数组1建立了一个和它的长度一样的存储空间，该存储空间的作用是——存储数组2中，可以和数组1中对应位置结合后和最小的数的下标。
例如：
数组1是：[1,2,3]，数组2是：[7,8,9,10,11]
那index数组就是[0,0,0]，这是index的初始化数据。表示数组1中，每个都是和数组2的第0个元素结合，可以得到（该元素和数组2每个元素结合后和的）最小值。
while语句执行一圈后，index数组就成了[1,0,0]，此时，数组对儿：1、7已经被压入ans数组。
这样，在下一次执行时，比较大小的几个数就是1+8（数组2的第1个元素），2+7，3+7，while之行后，index变成了[2,0,0]…
依次类推。

最后ans即为题目所求。