題目網址：https://leetcode.cn/problems/rotate-array/

題意：給一 array nums, 將其往右旋轉 k 次, 其中 k 為非負整數。

Solution 1：

想法：用額外的 array 來記住原本的 nums 來進行旋轉, 由於 k 有可能會大於 n, 所以先將 k 做 mod 運算

e.g. nums = [1, 2, 3], k = 4, 其實 k 等價於 4 % 3 = 1

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        const vector<int> tmp = nums;

        k %= n;
        for (int i = 0; i < n; ++i) {
            nums[(i + k) % n] = tmp[i];
        }
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ tmp

Solution 2：

想法：將 nums 分成兩個部分, 旋轉後不會溢出 nums 的、旋轉後會溢出 nums 的。發現可以先將 nums 進行 reverse, 然後針對那兩個 group 再做一次 reverse 即為所求

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

private:
    void reverse(vector<int>& nums, int left, int right){
        while (left < right) {
            swap(nums[left++], nums[right--]);
        }
    }
};
  • time：$O(n)$ ➔ reverse 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間