LeetCode Rotate Array：數組循環右移 K 位

問題描述

將長度為 n 的數組向右循環移動 k 位。如 n=7, k=3，[1,2,3,4,5,6,7] → [5,6,7,1,2,3,4]。要求原地修改，O(1) 額外空間。

解法一：額外數組保存後 k 個（O(k) 空間）

將後 k%n 個元素拷貝到臨時數組，前 n-k 個元素整體後移 k 位，再將臨時數組拷回前 k 位。

解法二：三次反轉（O(1) 空間，推薦）

1. 反轉前 n-k 個元素。2. 反轉後 k 個元素。3. 反轉整個數組。原理：循環移動等價於兩段反轉後整體反轉。

代碼實現 (C++)

class Solution {
public:
    void rotate(vector& nums, int k) {
        int n = nums.size();
        k %= n;
        if (k == 0) return;
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

複雜度分析

• 時間複雜度：O(n)。
• 空間複雜度：O(1)。

總結

三次反轉法巧妙利用反轉操作實現原地循環移動，代碼極其簡潔，是面試首選解法。