C++速通LeetCode中等第10题-轮转数组（四种方法）

方法一：巧用deque双向队列容器

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        deque<int> q;
        int tmp;
         
        if(nums.size() > 1)
        {
            for(auto num:nums) q.push_back(num);
        
            for(int i = 0;i < k;i++)
            {
                tmp = q.back();
                q.pop_back();
                q.push_front(tmp);
            }
            for(int j = 0;j < nums.size();j++)
            {
                nums[j] = q[j];
            } 
        }
    }
};

方法二： 先在vector尾部添加，后删除头部（超出时间限制）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        while(k >= nums.size()) k -= nums.size();
        k = nums.size() - k;
        for(int i = 0;i < k; i++)
        {
            nums.push_back(nums[i]);
        }
        int j = 0;
        for(auto it = nums.begin();j < k;j++)
        {
            it = nums.erase(it);
        }
    }
};

方法三： 额外vector存放数组

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) {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};

方法四：翻转（空间复杂度O(1))

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};