2017年9月21日 星期四

[演算法] 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']

資料來源

0 意見:

張貼留言