本文介绍了合并两个数组并排序最后一个的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在一次采访中,我被问到以下问题。
我得到了两个数组,它们都已排序。



BUT



数组1将几乎没有-1,而数组2的总数就是数组1中的-1总数。



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



  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 ++; }} //对于console.log( array-1 + array-2,arrayOne); bubbleSort(arrayOne); console.log( Sorted array,arrayOne);} // puzzle01puzzle01(); //冒泡排序的实现,用于对//合并的array函数进行排序// bubbleSort(arrayOne){var nextPointer = 0,temp = 0,hasSwapped = false;做{hasSwapped = false; for(var x = 0; x< arrayOne.length; x ++){nextPointer = x + 1;如果(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]
排序数组[1,3,6,9,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],

第一步:我会遍历arrayTwo。取下一个元素(即 1)并与arrayOne的下一个元素(即 3)进行比较。



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



OR



步骤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]



等。



at最后我将得到输出

  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){//遍历array2

do {
if(arrayOne [array1Counter] === -1){//如果-1发生在array1中
hasMinusOneOccurred = true;

//在array1当前位置交换数字
//在array2当前位置交换
swap(arrayOne,arrayTwo,array1Counter,array2Counter);

//重新检查当前值是否大于其他值
// array1
if(recheckAndSort(arrayOne,array1Counter)=== true){
array1Counter = -1; //从开始
重新检查array1} else {
//重新检查当前的array1计数器,这样做1倒退
// //即使计数器是递增它指向当前的
//数字本身
array1Counter--;
}

}否则if(arrayOne [array1Counter]> arrayTwo [array2Counter]){
swap(arrayOne,arrayTwo,array1Counter,array2Counter);
} else {
array1Counter ++;
继续;
}

array1Counter ++;
} while(hasMinusOneOccurred === false); //做完

array2Counter ++;
hasMinusOneOccurred = false;

} //同时结束

console.log( Sorted array,arrayOne);

函数swap(arr1,arr2,arr1Index,arr2Index){
var temp = arr2 [arr2Index];
arr2 [arr2Index] = arr1 [arr1Index];
arr1 [arr1Index] = temp;
} //交换结束

//如果在array1中出现-1,则调用此方法
函数recheckAndSort(arrayOne,array1Counter){
var isGreaterVal = true ,
prevCounter = 0,
nextCounter = 0,
temp = 0,
recheckFromStart = false;


if(array1Counter === 0){//如果-1出现在array1的第一个位置。

//检查是否在第一个位置发生-1的记录
//如果是,则从开始
迭代array1 recheckFromStart = true;

//重复向前检查是否有任何数字小于当前位置,
//如果是,则向前移动
for(var j = 0; isGreaterVal; j ++){
nextCounter = j + 1;

if(arrayOne [nextCounter] === -1){
//在当前
的下一个之间交换array1的数量swap(arrayOne,arrayOne,nextCounter,j);
isGreaterVal = true;

}否则if(arrayOne [nextCounter]< arrayOne [j]){
//在当前
的下一个之间交换array1的数量swap(arrayOne,arrayOne,nextCounter, j);
isGreaterVal = true;

}其他{
isGreaterVal = false;
}

} //

}的其他结尾{//如果-1出现在array1的中间位置并被交换,则
//向后迭代以检查是否存在小于当前位置的数字,
//如果是,则向后移位。
for(var i = array1Counter; isGreaterVal; i-){
prevCounter = i -1;

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

//在先前的
和当前的
之间交换array1的数量swap(arrayOne,arrayOne, prevCounter,i);
isGreaterVal = true;
} else {
isGreaterVal = false;
}

} //
的结尾}

return recheckFromStart;
} // recheckAndSort
} //拼图结束02

之后调用上述函数

  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]
排序数组[1,3,6,10,11,15,17,32,34,42,56]

谢谢。

解决方案

其中有一个干净的O(N)位置解决方案。



首先移动所有 -1 arrayOne (下面的-)显示在最前面。



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

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

包装:

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

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

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

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

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

$ b 3,-,-,- ,6,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
-,-,2 8

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

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

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

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


In an interview I was asked the following question.I am given two arrays, both of them are sorted.

BUT

Array 1 will have few -1's and Array 2 will have total numbers as the total number of -1's in Array 1.

So in the below examplearray1 has three -1's hence array2 has 3 numbers.

let say

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

Both of the arrays will be sorted.

Now I have to write a program that will merge arrayTwo in arrayOne by replacing -1's, and arrayOne should be in sorted order.

So the output will be

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

Sorting should be done without use of any sort API.

I have written a following code

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

The output of the above code is

 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 ]

From the above code you can see, I have first merged the two arrays and than sorted the final one.

Just wanted to know,Is there a better solution.

Is there any flaw in my solution.

Please let me know, it will be helpfull.

After reading all your very helpful comments and answers, I found was able to figure out a more faster solution.

Let us take an example

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

Step1: I will iterate through arrayTwo. Take the next element (i.e. '1') and compare with next element of arrayOne (i.e. '3') and compare.

step 2a : If element of array1 is greater than element of array2 than swap array elements. Now go to next element of array1.

OR

step 2b : If element of array1 is equal to -1 than swap array elements. Now go to next element of array2.

step 3: Go to step 1.

So

in the above example

first iteration, array1 = [1,6,-1,11,...] array2 = [3,10,17,56]

second iteration, array1 = [1,3,-1,11,..] array2 = [6,10,17,56]

third iteration, array1 = [1,3,6,11..] array2 = [-1,10,17,56]

fourth iteration array1 = [1,3,6,10,..] array2 = [-1,11,17,56]

and so on.

at the end I will get the output

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

Please find the code below,

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

After calling the above function

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

The output of above code is,

 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 ]

Thanks.

解决方案

There is a clean O(N) in-place solution.

First "pack" arrayOne by moving all -1 (-- below) to the front. This takes a single backward pass.

Then perform a merge by iteratively moving the smallest element among arrayTwo and the tail of arrayOne and overwriting the next --. The gap will narrow down but there will always remain room for the elements of arrayTwo.

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

Packing:

 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

Merging:

  --, --, --,  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
  --, --, --

这篇关于合并两个数组并排序最后一个的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-14 11:07