#77 数组中数据归并


  • 0
    administrators

    有一个数组,这个数组从两个地方开始升序,一个是开始,一个是中间。例如:

    [10, 21, 32, 11, 16, 40] // 从 0 和 3 开始升序
    [1, 5, 10, 11, 3, 4, 8, 12, 30] // 0 和 4 开始升序
    

    请你完成 merge 函数,可以把类似上面的数组变成一个完全升序的数组(直接修改原来的数组)。你不能用 sort 方法,并且只能使用一次循环。


  • 0

    const move = (arr, i, j) => arr.splice(i, j - i + 1, ...[arr[j], ...arr.slice(i, j)])
    const merge = arr => {
      let j = arr.length / 2 | 0
      for (let i = 0; i < arr.length; i++) {
        if (j <= i) return
        if (arr[i] > arr[j]) move(arr, i, j++)
      }
    }
    

    大抵是原地归并排序罢


  • 0
    administrators

    @CodeHz 感觉这个 splice 估计会把数组元素搬动次数比较多


  • 0

    @ScriptOJ 无论如何,移动元素的位置都是要用一个循环的。。。splice这样写还可以让引擎优化一下,如果要一起移动的话,那么就得显式的写一个循环来找了。。。即使用find这样规避过去,也没有改变要循环的本质,还不如写的短一点好。。。


  • 0
    administrators

    @CodeHz 也不一定要原地排序。


  • 0

    @ScriptOJ 你的意思是先用一个临时数组存放直接归并的结果,然后再splice回去对吧。。。


  • 0
    administrators

    @CodeHz 先 copy 到另外一个数组。循环在新的数组中进行对比,归并结果放回原来数组。不需要 splice 呀


  • 0

    一次循环(o(n)) + 接修改原来的数组(原地排序)的要求做不到吧?
    复制出来 -> 非原地
    用 splice, reverse -> 就是多次循环了


  • 1

    const reverse = (arr: Array<{}>, begin: number, end: number) => {
      while (begin < end) [arr[begin++], arr[end--]] = [arr[end], arr[begin]]
    }
    
    const merge = (arr: number[]): number[] => {
      const len = arr.length
      let pivot = len >> 1
      let i = 0
      let j = pivot
    
      while (i < j && pivot < len) {
        while (arr[i] < arr[j]) i++
        while (arr[j] <= arr[i]) j++
        reverse(arr, i, pivot - 1)
        reverse(arr, pivot, j - 1)
        reverse(arr, i, j - 1)
        ; [i, pivot] = [pivot, j]
      }
      return arr
    }
    

    像这种,三个 while,但只遍历一次的,被认为是遍历三次,也是很没道理。


  • 0

    感觉很蠢但是可以通过

    const merge = (arr) => {
    	let i = 0, len = arr.length, mid = len >> 1 , n = mid, arr2 = []
    	while(i < n && mid < len) {
    		if(arr[i] < arr[mid]){
    		  arr2.push(arr[i++])
    		} else {
    			arr2.push(arr[mid++])
    		}
    	}
    	if(mid == len) {
    		arr.splice(0, 0, ...arr.splice(- len + n))
    	}
    	arr.splice(0, arr2.length, ...arr2)
    }
    

  • 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++;
          }
        }
      }
    }
    

登录后回复
 

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