logo标签列表

将两个已排序的数组合并为一个

javascriptarraysalgorithmsorting
4

您好，我被问了以下问题。

给定两个数组，即array1和array2。它们都按排序顺序包含数字。

Array1还包含-1，例如;在array1中有多少个数字，在array2中就有多少个-1。

例如如下所示：

array1 = [-1,-1,-1,-1,56,78,90,1200];
array2 = [1,4,5,1000]

我需要编写一个程序，将上述数组合并为一个数组，该新数组按照排序顺序包含两个数组中的数字，但不包括 -1。
以下是我的代码：
 puzzle04([3,6,-1,11,15,-1,23,34,-1,42],[1,12,28]);
 puzzle04([3,6,-1,11,15,-1,23,34,-1,42],[7,19,38]);
 puzzle04([3,6,11,15,32,34,42,-1,-1,-1,-1],[1,10,17,56]);
 puzzle04([-1,-1,-1,-1,3,6,11,15,32,34,42],[1,10,17,56]);
 puzzle04([-1,-1,-1,-1,3,6,11,15,32,34,42],[56,78,90,100]);
 puzzle04([12,34,65,-1,71,85,90,-1,101,120,-1,200],[24,37,94]);
 puzzle04([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);
 puzzle04([-1,-1,-1,56,78,90,112],[1,4,5]);
 puzzle04([-1,-1,-1,-1,56,78,90,112],[1,4,5,1000]);
 puzzle04([-1,-1,-1,-1,56,78,90,1200],[1,4,5,1000]); 

 function puzzle04(array1,array2){

    var outputArray = [],
        array1Counter = 0, // counter for array1
        array2Counter = 0, // counter for array2
        isArray2NumPlaced = false, // has number from array2 found its position in output array ?       
        areAllArray2NumsFilled = false; // is number pushed in output array

    // iterating through array2 loop    
    for(array2Counter = 0; array2Counter < array2.length; array2Counter++){

        // iterating through array1 loop
        for(; (isArray2NumPlaced === false); array1Counter++){

            // -1 encountered in array1
            if(array1[array1Counter] === -1){ 
                continue;

            // if array1 number is less than array2 number
            // then push array1 number in ouput array   
            }else if(array1[array1Counter] < array2[array2Counter]){

                outputArray.push(array1[array1Counter]);                

            }else{ // array2 number is less then array1 number

                // add array2 number in output array until
                // all array2 numbers are not added in output array.
                if(areAllArray2NumsFilled === false){
                    outputArray.push(array2[array2Counter]);    
                }               


                // is array2 number pushed in output array ?
                isArray2NumPlaced = true;

            }// end of if-else

            // if all the array2 numbers are added in output array
            // but still array1 numbers are left to be added
            if(isArray2NumPlaced === true 
            && array2Counter === (array2.length - 1) 
            && array1Counter <= (array1.length - 1)){

                outputArray.push(array1[array1Counter]);    

                // set the below flag to false so that,
                // array1 loop can iterate
                isArray2NumPlaced = false;

                // all the numbers of array2 are entered in output array
                areAllArray2NumsFilled = true;

            }// end of if

        }// array1 for-loops ends



        array1Counter--;
        isArray2NumPlaced = false;

    }// array2 for-loops ends


    console.log("final ",outputArray);  
}

以上代码的输出如下：
final  [ 1, 3, 6, 11, 12, 15, 23, 28, 34, 42 ]
final  [ 3, 6, 7, 11, 15, 19, 23, 34, 38, 42 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 3, 6, 11, 15, 32, 34, 42, 56, 78, 90, 100 ]
final  [ 12, 24, 34, 37, 65, 71, 85, 90, 94, 101, 120, 200 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 1, 4, 5, 56, 78, 90, 112 ]
final  [ 1, 4, 5, 56, 78, 90, 112, 1000 ]
final  [ 1, 4, 5, 56, 78, 90, 1000, 1200 ]

当我向代码评审者展示我的代码时，他说我使用了太多的布尔变量，代码可以更简单。
我尽力改进了，但是没有任何线索。
您能否请建议我解决上述问题的更好方法？
注：不能使用任何现成的排序方法或预写API来解决以上练习。
7
这可能更适合在codereview.stackexchange.com上提问。 - Alexander Nied
1
创建一个函数，将数组合并（不考虑值）并进行排序。大多数排序算法可以用比所呈现的更少的代码实现，并且并不那么复杂。 - Skerkles
按照@Skerkles的指示去做，你可能会得到一个O(nm * log(nm))的时间复杂度，这并不是太糟糕。 - Sean Kwon
1
这个问题与http://stackoverflow.com/questions/42531614/merge-two-arrays-and-sort-the-final-one/42531787#42531787有何不同？ - Nina Scholz
可能是合并两个数组并排序最终结果的重复问题。 - le_m
显示剩余4条评论
9个回答
4

您只需遍历两个数组，取两个值中较小的一个，并将其添加到输出列表中。一旦您添加了其中一个数组的所有值，则另一个数组的剩余部分都比该值大，可以一次性添加。

function merge(x, y) {
    var i = 0;
    var j = 0;
    var result = [];

    while (i < x.length && j < y.length) {
        // Skip negative numbers
        if (x[i] === -1) {
            x += 1;
            continue;
        }
        if (y[j] === -1) {
            y += 1;
            continue;
        }

        // Take the smaller of the two values, and add it to the output.
        // Note: the index (i or j) is only incremented when we use the corresponding value
        if (x[i] <= y[j]) {
            result.push(x[i]);
            i += 1;
        } else {
            result.push(y[j]);
            j += 1;
        }
    }

    // At this point, we have reached the end of one of the two arrays. The remainder of
    // the other array is all larger than what is currently in the output array

    while (i < x.length) {
        result.push(x[i]);
        i += 1;
    }

    while (j < y.length) {
        result.push(y[j]);
        j += 1;
    }

    return result;
}
如果你有未知数量的数组会怎样？ - Kennet Celeste
相同的原则可以应用在这里，但你需要使用一个索引数组，而不是两个变量 i 和 j。此外，在每次迭代中获取最小数可能会变得相当复杂。我会将每个数组的当前数字存储在一个最小堆中，这样在每次迭代中取最小数就成为一个 O(1) 操作，并且在每次迭代中添加来自该数组的下一个数字就成为一个 O(log N) 操作。 - Andrew Williamson
1
要将两个已排序的数组拼接在一起，您可以按照下面所示的方法进行操作。要添加省略特定值的功能，您可以使用.filter()在合并数组之前消除这些元素。 

function stitch(left, right) {
    left = left.filter(function (elem) { return elem !== -1; });
    right = right.filter(function (elem) { return elem !== -1; });
    var results = [];
    while (left.length && right.length) {
        if (left.length && right.length && (left[0] <= right[0])) {
            results.push(left.shift());
        } else {
            results.push(right.shift());
        }
    }

    return results.concat(left, right);
}

console.log(stitch([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 12, 28]));

1

如果你考虑到了特殊的-1排除条件，你可以按照以下方式将多个已排序数组合并为一个：

function merger(a,b,_,__,r = []){
  return !a.length ? !b.length ? r
                               : r.concat(b.filter(n => n > -1))
                   : !b.length ? r.concat(a.filter(n => n > -1))
                               : a[0] > -1 ? b[0] > -1 ? a[0] > b[0] ? (r.push(b[0]), merger(a,b.slice(1),_,__,r))
                                                                     : (r.push(a[0]), merger(a.slice(1),b,_,__,r))
                                                       : merger(a,b.slice(1),_,__,r)
                                           : merger(a.slice(1),b,_,__,r);
}

var arrs =  [[3,6,-1,11,15,-1,23,34,-1,42],[1,12,28],[3,6,-1,11,15,-1,23,34,-1,42],[7,19,38],[3,6,11,15,32,34,42,-1,-1,-1,-1],[1,10,17,56],[-1,-1,-1,-1,3,6,11,15,32,34,42],[1,10,17,56],[-1,-1,-1,-1,3,6,11,15,32,34,42],[56,78,90,100],[12,34,65,-1,71,85,90,-1,101,120,-1,200],[24,37,94],[3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56],[-1,-1,-1,56,78,90,112],[1,4,5],[-1,-1,-1,-1,56,78,90,112],[1,4,5,1000],[-1,-1,-1,-1,56,78,90,1200],[1,4,5,1000]],
     res = arrs.reduce(merger);
console.log(JSON.stringify(res));

注意：不能使用任何现成的排序方法或预先编写的API来解决上述练习。 - Nina Scholz
@Nina Scholz，我刚刚自己写了几分钟前的代码。如果之前已经有人实现过，对不起。 - Redu
1
function merge(array1, array2)
{
    int i = 0, j = 0;
    array3; //answer
    while ( i<array1.size() and j<array2.size() ){

        if (array1[i] == -1 ) //ignore -1
        {   ++i; continue; }
        if (array2[j] == -1 ) //ignore -1
        {   ++j; continue; }

        if ( array1[i] < array2[j] ) { //choose the minor
            array3.push( array1[i] );
            ++i;
        }
        else {
            array3.push( array2[j] );
            ++j;    
        }
    }

    //if some array has elements still
    while (i < array1.size() )
        array3.push(array1[i]);
    while (j < array2.size() )
        array3.push(array1[j]);

    return array3
}
1
function merge(array1, array2){
        var array = [];
        var i = 0;
        var j = 0;
        while(i < array1.length || j < array2.length){
            if(array1[i] === -1){
                i++;
                continue;
            }
            if(array1[i] && (!array2[j] || array1[i] <= array2[j])){
                array.push(array1[i]);
                i++;
            } else if(array2[j] && (!array1[i] || array2[j] <= array1[i])){
                array.push(array2[j]);
                j++;
            }
        }
        return array;
    }
你可以使用 Array.prototype.shift() 代替记住索引，这样做能够简化解决方案。另外，此方法不检查 array2[i] === -1 的情况。因此，如果数组array2中出现-1，则它将出现在返回的数组中，这是不希望出现的。 - mhodges
1
尝试这个。
function puzzle04(arr1, arr2) 
{    
    var result = [];
    var final = [];
    var arr_concat = arr1.concat(arr2).filter(function (value) {
       return value != -1;
    });

    arr_concat.forEach(function(x) { 
        if(!result[x]) { 
            result[x] = []; 
            result[x].push('super sort'); 
        }
        else { 
            result[x].push('super sort'); 
        } 
    });

    result.forEach(function(k, v) { 
        k.forEach(function(x) {
            final.push(v); 
        }); 
    });

    console.log(final);
}
1
你所描述的是 归并排序 ：
function puzzle04(array1, array2) {
  return mergeSortWithoutMinusOnes(array1.concat(array2))
}

function mergeSortWithoutMinusOnes(items){

  if (items.length < 2) {
    return items;
  }

  var middle = Math.floor(items.length / 2),
      left    = items.slice(0, middle),
      right   = items.slice(middle);

  return mergeWithoutMinusOnes(mergeSortWithoutMinusOnes(left), mergeSortWithoutMinusOnes(right));
}

function mergeWithoutMinusOnes(left, right){
  var result  = [],
      il      = 0,
      ir      = 0;

  while (il < left.length && ir < right.length){
    if (left[il] < right[ir]){
      if (left[il] === -1) {
        il++;
      } else {
        result.push(left[il++]);
      }
    } else {
      if (right[ir] === -1) {
        ir++
      } else {
        result.push(right[ir++]);
      } 
    }
  }

  return result.concat(left.slice(il)).concat(right.slice(ir));
}

来自: https://github.com/nzakas/computer-science-in-javascript/blob/master/algorithms/sorting/merge-sort-recursive/merge-sort-recursive.js ，经过修改以忽略负数。

0

您可以在单个循环中迭代arrayOne，然后是arrayTwo。

思路是将目标索引与实际索引分开。第一个循环忽略-1并保留目标索引。

如果实际值大于arrayTwo的第一个值，则交换两个值，并通过迭代和与更大的值交换来在arrayTwo中占据排序位置。

然后，将实际项分配给目标索引。

两个索引都会增加。

最后，将所有arrayTwo项目添加到arrayOne中。

function puzzle04(arrayOne, arrayTwo) {
    var i = 0, j, l = 0;
    while (i < arrayOne.length) {
        if (arrayOne[i] === -1) {
            i++;
            continue;
        }
        if (arrayTwo[0] < arrayOne[i]) {
            [arrayOne[i], arrayTwo[0]] = [arrayTwo[0], arrayOne[i]];
            j = 0;
            while (arrayTwo[j] > arrayTwo[j + 1]) {
                [arrayTwo[j], arrayTwo[j + 1]] = [arrayTwo[j + 1], arrayTwo[j]];
                j++;
            }
        }
        arrayOne[l++] = arrayOne[i++];
    }
    j = 0;
    while (l < arrayOne.length) {
        arrayOne[l++] = arrayTwo[j++];
    }
    return arrayOne;
}

console.log(puzzle04([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 12, 28]));
console.log(puzzle04([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [7, 19, 38]));
console.log(puzzle04([3, 6, 11, 15, 32, 34, 42, -1, -1, -1, -1], [1, 10, 17, 56]));
console.log(puzzle04([-1, -1, -1, -1, 3, 6, 11, 15, 32, 34, 42], [1, 10, 17, 56]));
console.log(puzzle04([-1, -1, -1, -1, 3, 6, 11, 15, 32, 34, 42], [56, 78, 90, 100]));
console.log(puzzle04([12, 34, 65, -1, 71, 85, 90, -1, 101, 120, -1, 200], [24, 37, 94]));
console.log(puzzle04([3, 6, -1, 11, 15, -1, 32, 34, -1, 42, -1], [1, 10, 17, 56]));
console.log(puzzle04([-1, -1, -1, 56, 78, 90, 112], [1, 4, 5]));
console.log(puzzle04([-1, -1, -1, -1, 56, 78, 90, 112], [1, 4, 5, 1000]));
console.log(puzzle04([-1, -1, -1, -1, 56, 78, 90, 1200], [1, 4, 5, 1000]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

0
我在开发我的dapp中的加密货币价格图表时遇到了这个问题。 我在这里添加了我的代码。您可以参考我的代码，从两个排序数组中创建一个排序数组。 

const array1 = [1, 4, 5, 6];
const array2 = [2, 3, 4, 5, 6, 7, 9, 10];
const array = [];
let index = 0;
for (const one of array1) {
  do {
    if (array2[index] > one) break;
    else if (array2[index] < one) array.push(array2[index]);
  } while (index++ < array2.length);
  array.push(one);
}

array.push(...array2.splice(index));
console.log(array);

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接