# 189. Rotate Array 反轉陣列

### 學習用途:
適用於大型數據, 挪動一部分資料
不必開銷 O(n) 空間暫存移動的部分

### 原地旋轉(不使用額外空間):

1.先將整個數組反轉
2.然後將前k個元素反轉
3.最後將剩餘的元素反轉

### 工作原理如下:

我們首先處理 k 可能大於數組長度的情況,使用 k %= n。
我們定義了一個輔助函數 reverse(),用於反轉數組的一部分。
然後我們執行三步反轉:
- 反轉整個數組
- 反轉前 k 個元素
- 反轉剩餘的元素

這個方法的巧妙之處在於,通過三次反轉,我們實現了`數組的旋轉`,而且是`原地操作`,不需要額外的空間。

### Complexity
- Time complexity: O(n)
- Space complexity: O(1)

O(1) 空間複雜度意味著算法使用的額外空間是固定的,不隨輸入規模增加。

在數組旋轉問題中,我們通過使用`固定數量的變量`和`原地操作`來實現 O(1) 空間複雜度。

相比之下,創建一個`新數組`來存儲結果`會導致 O(n)` 的空間複雜度。

O(1) 空間複雜度的算法在`處理大規模數據`時特別有優勢,因為它們的內存使用不會隨輸入增加。

### Code

function rotate(nums: number[], k: number): void {
    const n = nums.length;
    
    // 處理 k > n 情況
    k %= n;

    // 處理反轉
    const reverse = (start:number, end:number) => {
        let tmp;
        for (let i = start; i < end; i++) {
            tmp = nums[i];
            nums[i] = nums[end];
            nums[end] = tmp;
            end--;
        }
    }

    // 三步反轉
    reverse(0, n-1);
    reverse(0, k-1);
    reverse(k, n-1);
};

### Sample
| 步驟 | 操作 | 結果 |
|------|------|------|
| 初始數組 | - | [1, 2, 3, 4, 5, 6, 7] |
| 步驟 1: 反轉整個數組 | reverse(0, n-1) | [`7, 6, 5, 4, 3, 2, 1`] |
| 步驟 2: 反轉前 k 個元素 | reverse(0, k-1) | [`5, 6, 7`, 4, 3, 2, 1] |
| 步驟 3: 反轉剩餘元素 | reverse(k, n-1) | [5, 6, 7, `1, 2, 3, 4`] |

注意：在這個例子中，k = 3

為什麼這個方法有效：

第一次反轉將所有元素顛倒，**把需要移動到前面的元素放到了數組的前端**，但順序是反的。
第二次反轉將前 k 個元素的**順序糾正**。
第三次反轉將剩餘元素的**順序糾正**。