JS实现合并多个有序数组

秒速五厘米 2023-05-30 03:52 1阅读 0赞

合并两个有序数组：  
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。（leetCode88）

说明:  
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。  
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

/**
     * @param {number[]} nums1
     * @param {number} m
     * @param {number[]} nums2
     * @param {number} n
     * @return {void} Do not return anything, modify nums1 in-place instead.
     */
    var merge = function(nums1, m, nums2, n) {
        
        let p1=0,p2=0,p=0;
        function arrayCopy(src,srcIndex,dest,destIndex,length){
        
            dest.splice(destIndex,length,...src.slice(srcIndex,srcIndex+length));
        }
        let nums1_copy=JSON.parse(JSON.stringify(nums1));
        while(p1<m&&p2<n){
        
            nums1[p++]=nums1_copy[p1]<nums2[p2]?nums1_copy[p1++]:nums2[p2++];
        }
        
        if(p1<m)arrayCopy(nums1_copy,p1,nums1,p1+p2,m+n-p1-p2);
        if(p2<n)arrayCopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);
    };

/**
     * @param {number[]} nums1
     * @param {number} m
     * @param {number[]} nums2
     * @param {number} n
     * @return {void} Do not return anything, modify nums1 in-place instead.
     */
    var merge = function(nums1, m, nums2, n) {
        
      let p1=m-1,p2=n-1,p=m+n-1;
      while(p1>=0&&p2>=0){
        
          nums1[p--]=nums1[p1]<nums2[p2]?nums2[p2--]:nums1[p1--];
      }
      function arrayCopy(src,srcIndex,dest,destIndex,length){
        
          dest.splice(destIndex,length,...src.slice(srcIndex,srcIndex+length));
      }
      // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为p2+1
      arrayCopy(nums2,0,nums1,0,p2+1)
    };

function fn(nums1,nums2){
        
      let len1=nums1.length,len2=nums2.length;
      let res=[],p1=0,p2=0;
      while(p1<len1&&p2<len2){
        
        if(nums1[p1]<nums2[p2])res.push(nums1[p1++])
        else if(nums1[p1]==nums2[p2]){
        
          res.push(nums1[p1++])
          p2++
        }else res.push(nums2[p2++])
      }
      while(p1<len1) res.push(nums1[p1++])
      while(p2<len2) res.push(nums2[p2++])
      return res
    }
    
    console.log(fn([1,1,2],[-1,0,4]))

假设有这样一个需求，一个数组的子元素全是有序数组，类似：

let arr= [[1, 2], [0, 3, 4,4,4,6,7,8,9,10], [-1, 4],[-1,3],[-1],[100,200],[5,1000,30000]];

最简单的方案就是：  
将数组整体合并，然后sort排序，代码如下：

let ret=arr.reduce((arr1,arr2)=>arr1.concat(arr2)).sort((a,b)=>a-b);
    ret=Array.from(new Set(ret));
    console.log(ret);

但是上面的代码没有充分利用数组子元素本身就是有序数组这一特性，我们利用“归并排序”算法，可以大大的提高类似数组的合并排序性能，代码(代码里面有详细注释)如下：  
归并排序的变体

function merge(arr){
        
      if(arr.length<1)return
      else if(arr.length==1)return arr[0]
      else{
        
        let child=arr.splice(0,1)[0]
        arr=merge(arr)
        let res=[],ci=0,ai=0
        while(ci<child.length&&ai<arr.length){
        
          if(child[ci]<arr[ai])res.push(child[ci++])
          else if(child[ci]==arr[ai]){
        
            res.push(child[ci++])
            ai++
          }else res.push(arr[ai++])
        }
        while(ci<child.length)res.push(child[ci++])
        while(ai<arr.length)res.push(arr[ai++])
        res=Array.from(new Set(res))//去重
        return res;
      }
    }
    
    console.log(merge([[1,1,2,3],[-1,0,3,5],[8,8,9,10]]))

参考：[javascript实现将多个有序数组合并为一个有序数组的算法][javascript]

[javascript]: https://segmentfault.com/a/1190000010302469