用雙指標來反轉陣列（筆記）

在看別人的解題說明時看到的一個寫法，因為簡單好理解印象很深刻，所以把它記錄下來。

執行的次數則是陣列中元素個數的一半。
對於很大的陣列來說的話，應該會非常有效率。

時間複雜度是 O(n) ，屬於線性時間。

func reverse<T>( _ array: inout [T]) {
    if array.isEmpty { return }
    var start = 0
    var end = array.count - 1
    
    while start < end {
        let temp = array[start]
        array[start] = array[end]
        array[end] = temp
        
        start += 1
        end -= 1
    }
}

稍微重構

抽 swap 出來

func reverse<T>( _ array: inout [T]) {
    if array.isEmpty { return }
    var start = 0
    var end = array.count - 1
    
    while start < end {
        swap(&array, start, end)
        
        start += 1
        end -= 1
    }
}

func swap<T>(_ array: inout [T], _ a: Int, _ b: Int) {
    if a >= array.count || b >= array.count {
        // Do nothing or assert with message over here
        return
    }
    let temp = array[a]
    array[a] = array[b]
    array[b] = temp
}

用用看

來餵個簡單的 test case

var array = [1, 3, 4, 5]
reverse(array)

執行完之後， array 就會變成 [5, 4, 3, 1] 。

圖解

[1, 3, 4, 5]
 s        e  (s=start) (end)

// swap the values
[5, 3, 4, 1]
 s        e

// moving the pointers
[5, 3, 4, 1]
    s  e

// swap the values
[5, 4, 3, 1]
    s  e

以上。