189. Rotate Array

題目 / Problem

中文： 給定一個整數陣列 nums，將陣列中的元素整體向右旋轉 k 步，其中 k 是非負整數。

English: Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Constraints / 限制： - 1 <= nums.length <= 10^5 - -2^31 <= nums[i] <= 2^31 - 1 - 0 <= k <= 10^5

Follow-up： 能否使用 O(1) 額外空間原地完成？/ Can you do it in-place with O(1) extra space?

Example / 範例：

Input:  nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
解釋 / Explanation:
  右移 1 步 / rotate 1 step:  [7,1,2,3,4,5,6]
  右移 2 步 / rotate 2 steps: [6,7,1,2,3,4,5]
  右移 3 步 / rotate 3 steps: [5,6,7,1,2,3,4]

名詞解釋 / Glossary

• 原地修改 / in-place：直接在輸入陣列上做修改，不另外開一個同樣大小的新陣列，額外空間只用幾個變數。Modifying the input array directly without allocating another array of the same size — only a constant number of helper variables.
• 反轉 / reverse：把一段陣列首尾互換，例如 [1,2,3,4] 反轉後變成 [4,3,2,1]。常用「雙指針」一頭一尾向中間靠攏。Swap elements from both ends moving inward, turning [1,2,3,4] into [4,3,2,1].
• 雙指針 / two pointers：用兩個索引變數同時追蹤陣列的不同位置，這裡用一個從左、一個從右往中間走來完成反轉。Two index variables tracking different positions; here one starts at the left, one at the right, moving toward each other.
• 取模運算 / modulo (%)：a % b 是 a 除以 b 的餘數。當 k 比陣列長度還大時，多餘的整圈旋轉沒有意義，所以用 k % n 把 k 縮到 [0, n) 範圍內。a % b is the remainder of a / b; we use k % n to discard full-cycle rotations that don't change the array.
• 指標 / pointer (C)：在 C 語言裡，int* nums 表示指向整數的指標，nums[i] 等同於 *(nums + i)，也就是讀取從 nums 起算的第 i 個元素。In C, int* nums is a pointer to int; nums[i] is shorthand for *(nums + i).
• vector<int> (C++)：C++ 標準函式庫的動態陣列，可以像普通陣列一樣用 [i] 取值，並用 .size() 取得長度。C++'s dynamic array; supports [i] indexing and .size().

思路

最直覺的暴力做法是「每次把陣列往右推一格，重複 k 次」，每次推一格需要 O(n) 的搬移，總共 O(n·k)，當 n 和 k 都到 10^5 時會超時。第二個自然想法是另開一個長度為 n 的新陣列 tmp，把原本第 i 位的元素放到 tmp[(i + k) % n]，最後再複製回去；這只要 O(n) 時間，但用了 O(n) 額外空間，沒有滿足 follow-up。要做到「原地、O(1) 空間」，關鍵觀察是：右移 k 步後，整個陣列恰好等於「後 k 個元素」接上「前 n - k 個元素」。基於這點有一個漂亮的「三次反轉」技巧——先把整個陣列反轉一次，原本最後 k 個元素就會跑到最前面（但順序是反的）；再分別把前 k 個和後 n - k 個各自反轉回正確順序，整體就完成了右移 k 步。注意 k 可能比 n 大，所以一開始要先做 k = k % n，否則反轉的切點會越界；當 k % n == 0 時陣列等於沒動，這個情況也被自動處理。

The brute-force "shift one step at a time, repeat k times" is O(n·k) and will TLE when both reach 10^5. The easy O(n)-space approach is to allocate a fresh array tmp and place nums[i] into tmp[(i + k) % n], then copy back — correct, but doesn't satisfy the O(1)-space follow-up. The clever in-place trick uses the observation that a right rotation by k simply concatenates "the last k elements" with "the first n - k elements." Reverse the whole array once — now the last k elements sit at the front, but in reversed order; reverse those first k elements to fix them, then reverse the remaining n - k to fix them, and the result is exactly the rotated array. We must normalize k with k %= n first, because k can exceed n and that would put the split point out of bounds; this also handles k == 0 (or any multiple of n) gracefully — every reverse is then a no-op or a full reverse paired with itself.

逐步走查 / Walkthrough

以 nums = [1,2,3,4,5,6,7]、k = 3 為例，n = 7，k % n = 3。三次反轉的過程：

反轉 [0, 6] 的雙指針細節 / two-pointer detail for step 1：

最終輸出 [5,6,7,1,2,3,4]，與預期相符。Final output matches the expected result.

Solution — C

/*
 * 演算法 / Algorithm: 三次反轉 / triple reverse.
 * 1) 整個陣列反轉 / reverse whole array
 * 2) 反轉前 k 個 / reverse first k
 * 3) 反轉後 n-k 個 / reverse last n-k
 * 時間 O(n)、空間 O(1)。Time O(n), space O(1).
 */

// 反轉 nums[l..r]（含兩端）/ reverse nums in range [l, r] inclusive
static void reverseRange(int* nums, int l, int r) {
    while (l < r) {                  // 雙指針未相遇就繼續 / continue while pointers haven't met
        int tmp = nums[l];           // 暫存左端值 / save left value into a temp
        nums[l] = nums[r];           // 把右端值搬到左邊 / move right value to left
        nums[r] = tmp;               // 把暫存的左端值放到右邊 / place saved value on the right
        l++;                         // 左指針向右移 / advance left pointer
        r--;                         // 右指針向左移 / move right pointer leftward
    }
}

// LeetCode 函式簽名：原地修改 nums，不需回傳 / signature: modify nums in place, no return value
void rotate(int* nums, int numsSize, int k) {
    int n = numsSize;                // 用較短的別名 n / shorter alias for length
    if (n <= 1) return;              // 長度 0 或 1 不必旋轉 / nothing to rotate
    k = k % n;                       // 把 k 縮到 [0, n) 避免多餘整圈 / drop full-cycle rotations
    if (k == 0) return;              // 旋轉 0 步等於不動 / k==0 means no change

    reverseRange(nums, 0, n - 1);    // 步驟 1：整個陣列反轉 / step 1: reverse all
    reverseRange(nums, 0, k - 1);    // 步驟 2：反轉前 k 個 / step 2: reverse first k
    reverseRange(nums, k, n - 1);    // 步驟 3：反轉後 n-k 個 / step 3: reverse the rest
}

Solution — C++

/*
 * 演算法 / Algorithm: 同 C 版本，三次反轉 / same triple-reverse trick.
 * 直接呼叫 STL 的 std::reverse，省得自己手寫雙指針。
 * Uses std::reverse from <algorithm> to avoid writing the swap loop manually.
 * Time O(n), Space O(1).
 */

#include <vector>      // std::vector：動態陣列容器 / dynamic array container
#include <algorithm>   // std::reverse：標準反轉函式 / standard reverse algorithm

class Solution {
public:
    // LeetCode 簽名：傳入引用 (&) 直接修改原陣列 / pass by reference to mutate caller's vector
    void rotate(std::vector<int>& nums, int k) {
        int n = nums.size();              // .size() 回傳元素個數 / number of elements
        if (n <= 1) return;               // 長度 0 或 1 不需處理 / nothing to do
        k %= n;                           // 等同 k = k % n，避免多餘整圈 / normalize k
        if (k == 0) return;               // 等同沒動 / no rotation needed

        // std::reverse(begin, end) 反轉左閉右開區間 [begin, end)
        // std::reverse takes a half-open iterator range [begin, end)
        std::reverse(nums.begin(), nums.end());            // 步驟 1：整段反轉 / reverse all
        std::reverse(nums.begin(), nums.begin() + k);      // 步驟 2：反轉前 k 個 / reverse first k
        std::reverse(nums.begin() + k, nums.end());        // 步驟 3：反轉剩下的 / reverse the rest
    }
};

複雜度 / Complexity

• Time: O(n) — 三次反轉每次最多走過陣列一半的元素，加總仍是線性；n 是 nums 的長度。% 與條件判斷都是 O(1)。Three reverses each touch at most half the array; combined work is linear in n (the array length).
• Space: O(1) — 只用了 tmp、l、r、k、n 等常數個變數，不依賴輸入大小。Only a constant number of scalar variables; no auxiliary array.

Pitfalls & Edge Cases

• 忘了 k %= n / forgetting to take k mod n：當 k >= n（甚至 k == n）時，k - 1 會超出陣列邊界，導致越界存取或結果錯誤。先取模才能把 k 縮到 [0, n)。If k >= n, indices like k - 1 go out of bounds; modulo normalizes k into [0, n).
• k == 0 或 n == 1 / k == 0 or single-element array：旋轉後與原陣列相同；本程式直接 return 避免做三次無意義的反轉，也不會出錯。Early return avoids wasted work and any off-by-one risk.
• 反轉區間的端點 / reverse range endpoints：注意我們用的是「左閉右閉」[l, r]（C 自寫版）與 C++ STL 的「左閉右開」[begin, end)，兩者邊界寫法不同，混用容易少 1 或多 1。The hand-written C helper uses inclusive [l, r]; std::reverse uses half-open [begin, end) — don't confuse them.
• 整數溢位 / integer overflow：題目允許元素到 2^31 - 1，但我們只做交換，不做加法或乘法，所以不會溢位。We only swap elements, never add — so the INT_MIN/INT_MAX range is safe.
• 誤以為要回傳新陣列 / expecting a return value：LeetCode 的 rotate 是 void，要原地改 nums；回傳新陣列會編譯失敗或測試失敗。The signature is void; mutate nums directly rather than returning a new array.