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

悠悠 2022-09-24 08:29 104阅读 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即为题目所求。