PJCHENder 未整理筆記

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

2017-09-26

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

keywords: temp variable, important

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

問題描述

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

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

前置閱讀

演算法實做

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

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

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

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

實做的方法會像這樣:

1
2
3
4
5
6
7
8
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 來反轉陣列的元素;但是這麼做還有一個問題,就是一開始第一個元素會和最後一個元素交換位置,可是跑到最後一個元素的時候,又和第一個元素交換位置,最後使的陣列沒有達到預期反轉的效果,因此我們的迴圈只要跑前一半就好

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

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
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']

資料來源

掃描二維條碼,分享此文章