189. Rotate Array

📘 題目敘述

給定一個整數陣列 nums，請將陣列往右旋轉 k 步。

換句話說：

每次旋轉 1 步，就是把最後一個元素搬到最前面
旋轉 k 步後，回傳旋轉完成的陣列結果（題目要求原地修改 nums）

條件限制

1 ≤ nums.length ≤ 10^5
-2^31 ≤ nums[i] ≤ 2^31 - 1
0 ≤ k ≤ 10^5

🧠 解題思路

我這份寫法的想法是：

與其真的做 k 次「把最後一個搬到最前面」，我直接找出「旋轉後的新陣列」會從原本哪個位置開始。

假設陣列長度是 n：

往右旋轉 k 步等價於往左旋轉 n - k 步（因為繞一圈會回到原本位置）

所以我只要先算出：

新陣列的第 0 個位置，應該對應到原本的哪個索引 pos

接著用 pos 往後一路放進新的陣列 rnums，並用 % n 讓索引循環即可。

所有變數

n：nums 的長度
k：題目要求往右旋轉的步數
pos：我用來指出「旋轉後第一個元素」在原陣列中的起始位置
rnums：暫存旋轉後結果的陣列，最後再整個指定回 nums

🪜 主要流程步驟

第一步：把 `k` 轉成等效的起始位置（重點）

因為 k 可能比 n 大，所以實際旋轉效果是以 k % n 為主。

我用這行去算起點：

pos = n - (k % n) 的概念
再把它整理成一定落在 [0, n-1] 的安全寫法

所以最後 pos 代表：

旋轉後的新陣列第 0 個元素，應該從原陣列的 nums[pos] 開始拿

第二步：依序把元素放進 `rnums`

接著我跑 n 次：

每次把 nums[pos] 放進 rnums
然後 pos++
再用 pos = pos % n 讓索引回到開頭（形成循環）

這樣就能做到「從起點開始繞一圈」，把所有元素按旋轉後順序收集完成。

第三步：把結果寫回 `nums`

最後我直接：

nums = rnums

完成題目要求的「修改原本陣列」的效果。

💡 整體邏輯總結

先找出旋轉後的起點 pos
從 pos 開始把元素依序搬到新陣列
用 % n 讓索引循環
最後把新陣列整個覆蓋回 nums

這樣時間是 O(n)，邏輯也很直觀。（但額外用了 rnums，所以空間是 O(n)。）

💻 程式碼實作

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int pos = (((n - k) % n) + n) % n;
        vector<int> rnums;
        for (int i = 0; i < n; i++) {
            rnums.push_back(nums[pos]);
            pos++;
            pos = pos % n;
        }
        nums = rnums;
    }
};

🔗 題目連結

https://leetcode.com/problems/rotate-array/