合并两个数组并对最后一个数组进行排序

Question

在一次面试中，我被问到了以下问题。我得到了两个数组，它们都是排序的。

但

数组1将有几个-1，数组2将有总数作为数组1中-1的总数。

因此，在下面的示例中，array1有三个-1，因此array2有三个数字。

让我们说

var arrayOne = [3,6,-1,11,15,-1,23,34,-1,42];
var arrayTwo = [1,9,28];

这两个数组都将被排序。

现在我必须编写一个程序，通过替换-1来合并arrayOne中的arrayTwo，并且arrayOne应该是有序的。

因此，输出将是

arrayOne = [ 1,3, 6, 9, 11, 15, 23, 28 ,34, 42 ]

排序应该在不使用任何排序API的情况下完成。

我写了下面的代码

​

function puzzle01() {
  var arrayOne = [3, 6, -1, 11, 15, -1, 23, 34, -1, 42];
  var arrayTwo = [1, 9, 28];
  var array1Counter = 0,
    isMerged = false;

  console.log(" array-1 ", arrayOne);
  console.log(" array-2 ", arrayTwo);

  for (var array2Counter = 0; array2Counter < arrayTwo.length; array2Counter++) {
    isMerged = false;
    while (isMerged === false && array1Counter < arrayOne.length) {

      if (arrayOne[array1Counter] === -1) {
        arrayOne[array1Counter] = arrayTwo[array2Counter];
        isMerged = true;
      }

      array1Counter++;
    }
  } //for

  console.log(" array-1 + array-2 ", arrayOne);
  bubbleSort(arrayOne);
  console.log(" Sorted array ", arrayOne);
} //puzzle01

puzzle01();

// implementation of bubble sort for sorting the 
// merged array
function bubbleSort(arrayOne) {
  var nextPointer = 0,
    temp = 0,
    hasSwapped = false;
    
  do {
    hasSwapped = false;
    for (var x = 0; x < arrayOne.length; x++) {
      nextPointer = x + 1;
      if (nextPointer < arrayOne.length && arrayOne[x] > arrayOne[nextPointer]) {
        temp = arrayOne[x];
        arrayOne[x] = arrayOne[nextPointer];
        arrayOne[nextPointer] = temp;
        hasSwapped = true;
      }
    } //for
  } while (hasSwapped === true);
} // bubbleSort

​

上述代码的输出为

 array-1  [ 3, 6, -1, 11, 15, -1, 23, 34, -1, 42 ]
 array-2  [ 1, 9, 28 ]
 array-1 + array-2  [ 3, 6, 1, 11, 15, 9, 23, 34, 28, 42 ]
 Sorted array  [ 1, 3, 6, 9, 11, 15, 23, 28, 34, 42 ]

从上面的代码可以看出，我首先合并了两个数组，然后对最后一个数组进行了排序。

只是想知道有没有更好的解决方案。

我的解决方案有没有什么缺陷。

请让我知道，这将是有帮助的。

在阅读了你所有非常有用的评论和答案后，我发现我能够找到一个更快的解决方案。

让我们举个例子

var arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1];
var arrayTwo = [1,10,17,56],

Step1:我将遍历arrayTwo。取下一个元素(即'1')与arrayOne的下一个元素(即'3')进行比较。

步骤2a :如果array1的元素大于array2的元素，则交换数组元素。现在转到array1的下一个元素。

或

步骤2b :如果array1的元素等于-1，则交换数组元素。现在转到array2的下一个元素。

步骤3:转到步骤1。

所以

在上面的例子中

第一次迭代，array1 = 1,6，-1,11，...array2 = 3,10,17,56

第二次迭代，array1 = 1,3，-1,11，.array2 = 6,10,17,56

第三次迭代，array1 = 1,3,6,11.array2 = -1,10,17,56

第四次迭代array1 = 1,3,6,10，.array2 = -1,11,17,56

诸若此类。

最后，我将得到输出

array1 = [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
array2 = [-1,-1,-1]

请找到下面的代码，

function puzzle02(arrayOne,arrayTwo){   
    var array1Counter = 0,
        array2Counter = 0,       
        hasMinusOneOccurred = false;

    console.log(" array-1 ",arrayOne);
    console.log(" array-2 ",arrayTwo);  


    while(array2Counter < arrayTwo.length){ // iterate through array2

        do{
            if(arrayOne[array1Counter] === -1){ // if -1 occurred in array1
                hasMinusOneOccurred = true;

                // swaping numbers at current position of array1
                // with current position of array2 
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);

                // recheck if the current value is greater than other values
                // of array1
                if(recheckAndSort(arrayOne,array1Counter) === true){
                    array1Counter = -1;// recheck array1 from start
                }else{
                    // recheck the current array1 counter, for doing so go 1 count back
                    // so that even if the counter is incremented it points to current
                    // number itself 
                    array1Counter--; 
                }

            }else if(arrayOne[array1Counter] > arrayTwo[array2Counter]){
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);
            }else{
                array1Counter++;
                continue;   
            }

            array1Counter++;            
        }while(hasMinusOneOccurred === false); // end of do-while

        array2Counter++;
        hasMinusOneOccurred = false;

    }//end of while

    console.log(" Sorted array ",arrayOne);

    function swap(arr1,arr2,arr1Index,arr2Index){
        var temp = arr2[arr2Index];
        arr2[arr2Index] = arr1[arr1Index];
        arr1[arr1Index] = temp;
    }// end of swap 

    // this method is call if -1 occures in array1
    function recheckAndSort(arrayOne,array1Counter){
        var isGreaterVal = true,
            prevCounter = 0,
            nextCounter = 0,
            temp = 0,
            recheckFromStart = false;


        if(array1Counter === 0){ // if -1 occurred at first position of array1.

            // flag to check if -1 occurrec at first position
            // if yes, iterate array1 from start
            recheckFromStart = true; 

            // iterate forward to check wether any numbers are less than current position,
            // if yes than move forward
            for(var j = 0; isGreaterVal; j++){
                nextCounter = j + 1;

                if(arrayOne[nextCounter] === -1){
                    // swaping numbers of array1 between next to current                    
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true; 

                }else if(arrayOne[nextCounter] < arrayOne[j]){
                    // swaping numbers of array1 between next to current
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true;

                }else{
                    isGreaterVal = false;
                }

             }//end of for

         }else{// if -1 occurred in the middle position of array1 and is been swaped then
            // iterate backwards to check if any number less then current position exists,
            // if yes than shift backwards.
            for(var i = array1Counter; isGreaterVal; i--){
                prevCounter = i - 1;

                if(arrayOne[prevCounter] > arrayOne[i]){

                    // swaping numbers of array1 between previous to current                    
                    swap(arrayOne,arrayOne,prevCounter,i);
                    isGreaterVal = true; 
                }else{
                    isGreaterVal = false;
                }

            }// end of for  
        }

        return recheckFromStart;        
    }// end of recheckAndSort
} // end of puzzle02

调用上述函数后

puzzle02([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);

上面代码的输出是，

 array-1  [ 3, 6, -1, 11, 15, -1, 32, 34, -1, 42, -1 ]
 array-2  [ 1, 10, 17, 56 ]
 Sorted array  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]

谢谢。

Answer 1

您可以尝试以下方法：

逻辑

• 创建一个新数组，该数组将对arrayTwo中的第一个元素进行returned.
• Check，并将其保存在一个变量中，例如val.
• Loop arrayOne，检查当前值是否大于val，将其推入数组，并将i的值减1，以检查当前元素的下一个值。
  • 现在检查当前元素。如果它小于0，则忽略它，否则将值推送到此数组。

​

function mergeAndSort(a1, a2) {
  var matchCount = 0;
  var ret = [];

  for (var i = 0; i < a1.length; i++) {
    var val = a2[matchCount];
    if (a1[i] > val) {
      ret.push(val)
      matchCount++
      i--;
      continue;
    }
    if (a1[i] > 0) {
      ret.push(a1[i]);
    }
  }
  console.log(ret.join())
  return ret;
}


var arrayOne = [3, 6, -1, 11, 15, -1, 23, 34, -1, 42]
var arrayTwo = [7, 19, 38];
var arrayThree = [1, 9, 28];
var arrayFour = [1,2,5]

mergeAndSort(arrayOne, arrayTwo)
mergeAndSort(arrayOne, arrayThree)
mergeAndSort(arrayOne, arrayFour)

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

​

注意：没有检查arrayTwo中的元素数量，因为它清楚地提到了它将是相同的。

Answer 2

有一个干净的O(N)就地解决方案。

首先通过将所有arrayOne (下面的--)移到前面来“打包”-1。这需要一次向后传递。

然后，通过迭代地在arrayTwo和arrayOne的尾部之间移动最小的元素并覆盖下一个--来执行合并。差距将会缩小，但始终会为arrayTwo的元素留出空间。

 3,  6, --, 11, 15, --, 23, 34, --, 42
 1,  9, 28

打包：

 3,  6, --, 11, 15, --, 23, 34, --, 42

 3,  6, --, 11, 15, --, 23, --, 34, 42

 3,  6, --, 11, 15, --, --, 23, 34, 42

 3,  6, --, 11, --, --, 15, 23, 34, 42

 3,  6, --, --, --, 11, 15, 23, 34, 42

 3, --, --, --,  6, 11, 15, 23, 34, 42

 --, --, --, 3,  6, 11, 15, 23, 34, 42

合并中：

  --, --, --,  3,  6, 11, 15, 23, 34, 42
   1,  9, 28

   1, --, --,  3,  6, 11, 15, 23, 34, 42
  --,  9, 28

   1,  3, --, --,  6, 11, 15, 23, 34, 42
  --,  9, 28

   1,  3,  6, --, --, 11, 15, 23, 34, 42
  --,  9, 28

   1,  3,  6,  9, --, 11, 15, 23, 34, 42
  --, --, 28

   1,  3,  6,  9, 11, --, 15, 23, 34, 42
  --, --, 28

   1,  3,  6,  9, 11, 15, --, 23, 34, 42
  --, --, 28

   1,  3,  6,  9, 11, 15, 23, --, 34, 42
  --, --, 28

   1,  3,  6,  9, 11, 15, 23, 28, 34, 42
  --, --, --

Answer 3

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

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

如果实际值大于arrayTwo的第一个值，则交换的值和arrayTwo中的值都通过迭代和与更大的值交换来进行排序。

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

两个索引都会递增。

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

​

function order(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(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [7, 19, 38]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 9, 28]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 2, 5]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [43, 44, 45]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

​