我正在嘗試就地反轉 JS 中的陣列（不使用額外的陣列）。我遞回地使用拆分合并（我首先將陣列分成兩半，然后分別重新排列每一半，然后組合兩個排列的結果）。如果陣列長度是奇數，問題似乎就會出現，在這種情況下，將存在一個包含單個專案的陣列和另一個包含兩個專案的陣列。
例子：
reverseArrayInPlace([1, 5, 0, 4, 6]) 應該像這樣作業：
1- reverseArrayInPlace([1,5,0]) -> 回傳以下呼叫
- reverseArrayInPlace([1, 5]) -> 回傳 [5, 1]
- reverseArrayInPlace([0]) -> 回傳 [0]
現在應該合并和交換第一次呼叫的兩個陣列。結果應該是 [0,5,1]
2- reverseArrayInPlace([4, 6]) -> 回傳 [6,4]
現在，呼叫 (1) 和呼叫 (2) 的結果必須合并和交換（也使用 concat）；這將使結果為：[6,4,0,5,1]。
我知道還有其他更簡單的方法，但我想知道為什么我的代碼沒有回傳正確的值。
let reverseArrayInPlace = ar => {
let splitArray = arr => {
if( arr.length === 1){
console.log('length = 1', arr);
return arr;
}
else if(arr.length === 2){
console.log('length = 2', arr);
let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
return arr;
}
else{
reverseArrayInPlace(arr);
//reverseArrayInPlace (ar2);
}
}
let mergeArray = (arr1, arr2) => {
console.log("Swapping : ", arr1, arr2);
console.log('Concated : ',arr2.concat(arr1));
if(arr1 === undefined)
return arr2;
else if(arr2 === undefined)
return arr1;
else
return arr2.concat(arr1);
}
let half = Math.ceil(ar.length / 2);
//console.log('half = ', half);
ar1 = splitArray(ar.slice(0, half));
ar2 = splitArray(ar.slice(half));
//console.log(arr1, arr2);
return mergeArray(ar1, ar2);
}
let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));
uj5u.com熱心網友回復：
在您的拆分陣列函式中，您錯過了一個return：
let splitArray = arr => {
if( arr.length === 1){
console.log('length = 1', arr);
return arr;
}
else if(arr.length === 2){
console.log('length = 2', arr);
let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
return arr;
}
else{
***RETURN*** reverseArrayInPlace(arr);
//reverseArrayInPlace (ar2);
}
}
我在 chrome 導航器中使用除錯器一步一步地走，注意到 ar1 在你step 1- reverseArrayInPlace([1,5,0]) -> returns the below calls
的上為空所以結果只包含第二部分：反轉的第二個陣列 [6,4]
uj5u.com熱心網友回復：
缺少的return陳述句是最初的問題，但更廣泛地說，這不是真正的就地演算法，因為它仍然通過創建新陣列來保留 O(n) 輔助記憶體。
對于就地演算法，應該沒有 O(n) 輔助記憶體使用。取而代之的是 makesplitArray和mergeArrayinplace 函式，以便在任何時候都只有一個陣列正在發生變異。
為此，您需要傳遞將成為拆分/合并操作主題的子陣列的開始/結束索引。
將空陣列情況包含在 : 的第一個基本情況中也更安全，splitArray因此使用<= 1代替=== 1。
這是您根據該想法更改的代碼：
let reverseArrayInPlace = (arr, start=0, end=ar.length) => {
let splitArray = (start, end) => {
if (end - start <= 1) return;
if (end - start === 2) {
let temp = arr[start]; arr[start] = arr[start 1]; arr[start 1] = temp;
}
else{
reverseArrayInPlace(arr, start, end);
}
}
let mergeArray = (start, mid, end) => {
arr.splice(start, 0, ...arr.splice(mid, end - mid));
}
let half = (start end) >> 1;
splitArray(start, half);
splitArray(half, end);
mergeArray(start, half, end);
return arr;
}
let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));您也不需要單獨處理第二個基本情況。如果您將這種情況作為遞回情況處理，則該操作將正常作業。
這是您根據該想法更改的代碼：
let reverseArrayInPlace = (arr, start=0, end=ar.length) => {
let splitArray = (start, end) => {
if (end - start > 1) reverseArrayInPlace(arr, start, end);
}
let mergeArray = (start, mid, end) => {
arr.splice(start, 0, ...arr.splice(mid, end - mid));
}
let half = (start end) >> 1;
splitArray(start, half);
splitArray(half, end);
mergeArray(start, half, end);
return arr;
}
let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391639.html
標籤：javascript 算法
上一篇：編程雙胞胎重聚的概率