跳至主要内容

[演算法] Reverse Array in Place：暫存變數的使用

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述​

在這次的練習中，我們要將輸入的陣列進行反轉，但有幾點需要注意的：

  1. 不能建立一個新的陣列，然後透過 push 的方式把新的元素內容推進去新陣列。
  2. 不能使用 Array.prototype.reverse() 這個方法。
function reverseArrayInPlace (arr) {...}

前置閱讀​

演算法實做​

第一個元素和倒數第一個元素對調​

為了達到陣列反轉的效果，我們有一個很特別，而且實務上也經常用到的技巧，第一個元素和倒數第一個元素對調；第二個元素和倒數第二個元素對調，以此類推...。

這個作法的技巧在於，我們要建立一個 暫存變數 ，邏輯有點像這樣：

let tempVar = 第一個元素;
第一個元素 = 倒數第一個元素;
倒數第一個元素 = tempVar; // 因為這時候第一個元素的值已經改變了，所以不能再直接代入第一個元素

實做的方法會像這樣：

function reverseArrayInPlace(arr) {
  for (let i = 0; i < arr.length; i++) {
    let tempVar = arr[i];
    arr[i] = arr[arr.length - 1 - i];
    arr[arr.length - 1 - i] = tempVar;
  }
  return arr;
}

和上次演算法 Algorithm: reverse words 使用到相同的技巧 arr.length - 1 - i 來反轉陣列的元素；但是這麼做還有一個問題，就是一開始第一個元素會和最後一個元素交換位置，可是跑到最後一個元素的時候，又和第一個元素交換位置，最後使的陣列沒有達到預期反轉的效果，因此我們的迴圈只要跑前一半就好：

for (let i = 0; i < (arr.length / 2); i++) {...}

完整程式碼​

function reverseArrayInPlace (arr) {
  for (let i = 0; i < arr.length / 2; i++) {
    let tempVar = arr[i]
    arr[i] = arr[arr.length - 1 - i]
    arr[arr.length - 1 - i] = tempVar
  }
  return arr
}

let arr = ['a', 'b', 'c', 'd']
console.log(reverseArrayInPlace(arr))      // ['d', 'c', 'b', 'a']

資料來源​