在一次采访中,我被问到以下问题。
我有两个数组,它们都已排序。
BUT
数组 1 将有少量 -1,数组 2 的总数将与数组 1 中 -1 的总数相同。
所以在下面的例子中
array1 有三个 -1,因此 array2 有 3 个数字。
let say
var arrayOne = [3,6,-1,11,15,-1,23,34,-1,42];
var arrayTwo = [1,9,28];
两个数组都将被排序。
现在我必须编写一个程序,通过替换 -1 将 arrayTwo 合并到 arrayOne 中,并且 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],
第 1 步:我将迭代 arrayTwo。取出下一个元素(即“1”)并与 arrayOne 的下一个元素(即“3”)进行比较并进行比较。
步骤 2a:如果 array1 的元素大于 array2 的元素,则交换数组元素。现在转到 array1 的下一个元素。
OR
步骤 2b:如果 array1 的元素等于 -1,则交换数组元素。现在转到 array2 的下一个元素。
步骤 3:转到步骤 1。
So
在上面的例子中
第一次迭代,
数组1 = [1,6,-1,11,...]
数组2 = [3,10,17,56]
第二次迭代,
数组1 = [1,3,-1,11,..]
数组2 = [6,10,17,56]
第三次迭代,
数组1 = [1,3,6,11..]
数组2 = [-1,10,17,56]
第四次迭代
数组1 = [1,3,6,10,..]
数组2 = [-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 ]
Thanks.