javascript - 将两个排序数组合并为一个

Question

您好，有人问我以下问题。

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

Array1 还包含 -1 例如； array2 中的数字与 array1 中的 -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 ]

当我向审阅者展示我的代码时，他说我使用了太多的 bool 变量，代码可以更简单。

我尽力即兴发挥，但没有得到任何线索。

能否请你建议我任何更好的方法来解决上述问题

注意:不能使用任何现成的排序方法或预先编写的api来解决上述练习。

Answer 1

您所要做的就是遍历两个数组，取两个值中较小的一个，并将其添加到输出列表中。一旦你添加了一个数组的所有内容，另一个数组的剩余部分就更大了，并且可以一次性添加。

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