问题描述
在一次采访中，我被问到以下问题。
我得到了两个数组，它们都已排序。
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);
} // bubbleSortThe 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
--, --, --
这篇关于合并两个数组并排序最后一个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！