https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        if (k == 0) return;
        int group = gcd(n, k);
        for (int i = 0; i < group; i++) {
            int pre = nums[i];
            int tmp = 0;
            int idx = i + k;
            while (idx != i) {
                tmp = nums[idx];
                nums[idx] = pre;
                pre = tmp;
                idx = (idx + k) % n;
            }
            nums[i] = pre;
        }
    }
};

Time Complexity: O(n)
Space: O(1)

非常好的面試題目，可以從 Space O(n) 優化到 Space O(1)。
優化核心關鍵，在旋轉 k 個的時候可以發現有組的關係。

  • Ex: nums = [0, 1, 2, 3], k = 2
    • 此時可以發現 (0, 2) 與 (1, 3) 為兩組，也就是 index 為 (0, 2) 與 (1, 3) 無關，他們獨自進行交換。

透過這個觀察可以對 nums 進行分組，總共的組數會是 GCD(len(nums), k) ，這部分可以稍微想一下，應該也不是很困難，這樣就可以在 space O(1) 下完成。