方法一:巧用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);}
};