跳转至

189 轮转数组

k没有说一定比数组长度小,所以需要做取余处理k = k % nums.size();

做法一

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for(int i = 0; i < n; i++){
            int idx = (i + k) % n;
            newArr[idx] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};

时间复杂度:\(O(n)\)

空间复杂度:\(O(n)\)

做法二

我也想不出怎么解释这个思路的来源,只能死记了

思路见https://leetcode.cn/problems/rotate-array/solutions/2784427/tu-jie-yuan-di-zuo-fa-yi-tu-miao-dong-py-ryfv/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

时间复杂度:\(O(n)\)

空间复杂度:\(O(1)\)