#77 数组中数据归并


  • 0

    const merge = (arr) => {
      let mid = ~~(arr.length / 2),
        start = 0,
        j = mid;
        len = arr.length,
        arr2 = [];
        
      while (start < mid && j < len) {
        if (arr[start] > arr[j]) { 
          arr2.push(arr[j++])
        } else {
          arr2.push(arr[start++])
        }
      }
      if (j < len) { 
        arr2.push(...arr.slice(j))
      }
      if (start < mid) {
        
        arr2.push(...arr.slice(start,mid))
      }
      arr.splice(0, len, arr2)
    }
    

    不知道为什么通不过???


  • 0

    虽然可能有点繁琐,但是便于理解,直接贴吧!(具体思路就是将有顺序的两截分别copy到两个新的数组,然后进行大小比较,赋值给原数组!)代码如下:

    const merge = (arr) => {
      let index, arr1, arr2;
      index = arr.length / 2;
      arr1 = arr.splice(0, index);
      arr2 = arr.splice(0);
      let i=j=k=0;
      while (j < arr2.length || i < arr1.length) {
        if (i === arr1.length) {
          arr[k] = arr2[j];
          k++;
          j++;
        }else if(j === arr2.length){
          arr[k] = arr1[i];
          k++;
          i++;
        }else {
          if (arr1[i] <= arr2[j]) {
            arr[k] = arr1[i];
            k++;
            i++;
          }else {
            arr[k] = arr2[j];
            k++;
            j++;
          }
        }
      }
    }
    

  • 0

    循环 剩余数据中最小的,然后删掉原来的数据,将最小数插入当前的位置

    const merge = (arr) => {
      arr.forEach((a,i)=>{
        let min = Math.min.apply(null,arr.slice(i))
        let index = arr.indexOf(min,i)
        arr.splice(index,1)
        arr.splice(i,0,min)
      })
    }
    

  • 0

    const merge = (arr) => 
    arr.forEach((v,i)=>{arr.push(...arr.splice(arr.indexOf(Math.min.apply(null,arr.slice(0,arr.length-i))),1));
    });

  • 0

    @qq1448896454#77 数组中数据归并 中说:

    const merge = (arr) => {
     arr.forEach((v,i)=>{
      let min = Math.min.apply(null,arr.slice(0,arr.length-i));
      let index = arr.indexOf(min);
      arr.push(...arr.splice(index,1));
     });
    }

  • 0

    没办法,天才

    const merge = (arr) => {
      const res = [];
      let min;
      while(arr.length) {
        min = Math.min.apply(null, arr);
        arr.splice(arr.indexOf(min), 1);
        res.push(min)
      }
      [].push.apply(arr, res);
    }
    

  • 0

    为什么我在谷歌浏览器上是正确的,提交的时候错了。。。
    function merge(arr) {
    let middle = Math.floor(arr.length / 2);
    let left = arr.splice(0, middle);
    let right = arr.splice(0, arr.length);
    console.log(arr);
    while (left.length>0 && right.length>0) {
    if (left[0] > right[0]) {
    arr.push(right.shift())
    } else if (left[0] === right[0]) {
    arr.push(right.shift());
    arr.push(left.shift())
    } else {
    arr.push(left.shift())
    }
    }
    return arr.concat(left, right);
    }


  • 0

    写成这样,还是厚着脸皮贴出来了

    const merge = (arr) => {
       var point = parseInt(arr.length / 2),
           arr1 = arr.slice(0, point),
           arr2 = arr.slice(point),
           num1 = 0, num2 = 0, num = 0;
       
       while (num < arr.length) {
           let a1 = arr1[num1], a2 = arr2[num2];
           if (num1 < arr1.length && num2 < arr2.length) {
               if (a1 < a2) {
                   arr[num] = a1;
                   num1++;
               }
               if (a1 === a2) {
                   arr[num] = a1;
                   num++;
                   num1++;
                   arr[num] = a2;
                   num2++;
               }
               if (a1 > a2) {
                   arr[num] = a2;
                   num2++;
               }
           }else if(num1 === arr1.length){
               arr[num] = a2;
               num2++;
           }else if(num2 === arr2.length){
               arr[num] = a1;
               num1++;
           }
           num++;
       }
    
       return arr;
    };

  • 0

    比较trick的写法, 利用同一个循环将前一个上升序列拷贝到tmp数组(mode == false), 并用归并的方式(mode == true)改变原数组.

    const merge = (arr) => {
      let i, j, k, mode = false, tl;
      const l = arr.length, tmp = [];
      for(i = j = k = 0; k < l;) {
        if(!mode && i < l) {
          tmp.push(arr[i]);
          if(arr[i + 1] < arr[i]) {
            mode = true;
            tl = tmp.length;
          }
          ++i;
          continue;
        }
        if(j === tl) arr[k++] = arr[i++];
        else if(i === l) arr[k++] = tmp[j++];
        else if(arr[i] < tmp[j]) arr[k++] = arr[i++];
        else arr[k++] = tmp[j++];
      }
    }
    
    

  • 0

    函数式,不知道这样行不行?

    function merge(arr1,arr2) {
         return quickSort([...new Set([...arr1,...arr2])])
    }
    // 数组部分排序
    function _quickSortAndParition(a,lo,hi) {
        if(hi<=lo) return;
        var j=partition(a,lo,hi);
        _quickSortAndParition(a,lo,j-1);
        _quickSortAndParition(a,j+1,hi);
        return a;
    }
    
    function partition(a,lo,hi) {
        let i=lo,j=hi+1; // i = 1, j = 3+1=4
        let v=a[lo]; // v = 21
        while (true){
            while (less(a[++i],v)) if(i==hi) break;
            while (less(v,a[--j])) if(j==lo) break;
            if(i>=j) break;
            exch(a,i,j)
        }
        exch(a,lo,j)  
        return j; 
    }
    // 交换数组元素
    function exch(a,i,j) {
        var t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    // 比较大小
    function less(v,w) {
        return v<w;
    }
    // 数组全排序
    function quickSort(a) {
        return _quickSortAndParition(a,0,a.length-1);
    }
    
    
    
    var arr1 = [10, 21, 32, 11, 16, 40];
    var arr2 = [1, 5, 10, 11, 3, 4, 8, 12, 30]
    console.log(merge(arr1,arr2))
    
    

  • 2

    一次循环的冒泡排序法~~ 通过了

    const merge = (arr) => /* TODO */
    {
      let length = arr.length;
      let temp; // 交换的中间值
      for(let i = 0; i< length;i++){
        if(arr[i] > arr[i+1]) {
          temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
        }
        if(i==length-1){
          i=-1;
          length--;
        }
      }
    }
    

  • 0

    0_1548920205053_#77 数组中数据归并.png


  • 0

    @SimonMa 一个 For 循环就一个 For 循环 ... O(n^2 ) 选择排序 , 估计是最慢的了...


  • 0

    const merge = (arr) =>{
      let [a,b]=[arr.slice(0,arr.length>>1),arr.slice(arr.length>>1,arr.length)];
      for(let i=0,j=0,k=0;i<arr.length;i++){
          if(j<a.length && k<b.length){
            if(a[j]<b[k]){
              arr[i]=a[j];
              j++;
            }else{
              arr[i]=b[k];
              k++;
            }  
          }else if(j==a.length){
            arr[i]=b[k++];
          }else{
            arr[i]=a[j++];
          }
      }
    }

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待