189. Rotate Array

Given an array, rotate the array to the right by  k  steps, where  k  is non-negative.

Example 1:

``````Input: [1,2,3,4,5,6,7] and _k_ = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
``````

Example 2:

``````Input: [-1,-100,3,99] and _k_ = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
``````

Note:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> t = nums;
for (int i = 0; i < nums.size(); ++i) {
nums[(i + k) % nums.size()] = t[i];
}
}
};
``````

1 2 3 4 5 6 7
1 2 3 1 5 6 7
1 2 3 1 5 6 4
1 2 7 1 5 6 4
1 2 7 1 5 3 4
1 6 7 1 5 3 4
1 6 7 1 2 3 4
5 6 7 1 2 3 4

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty() || (k %= nums.size()) == 0) return;
int start = 0, idx = 0, pre = 0, cur = nums[0], n = nums.size();
for (int i = 0; i < n; ++i) {
pre = cur;
idx = (idx + k) % n;
cur = nums[idx];
nums[idx] = pre;
if (idx == start) {
idx = ++start;
cur = nums[idx];
}
}
}
};
``````

1 2 3 4 5 6 7
4 3 2 1 5 6 7
4 3 2 1 7 6 5
5 6 7 1 2 3 4

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty() || (k %= nums.size()) == 0) return;
int n = nums.size();
reverse(nums.begin(), nums.begin() + n - k);
reverse(nums.begin() + n - k, nums.end());
reverse(nums.begin(), nums.end());
}
};
``````

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty() || (k %= nums.size()) == 0) return;
int n = nums.size();
for (int i = 0; i < n - k; ++i) {
nums.push_back(nums[0]);
nums.erase(nums.begin());
}
}
};
``````

1 2 3 4 5 6 7
5 2 3 4 1 6 7
5 6 3 4 1 2 7
5 6 7 4 1 2 3
5 6 7 1 4 2 3
5 6 7 1 2 4 3
5 6 7 1 2 3 4

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty()) return;
int n = nums.size(), start = 0;
while (n && (k %= n)) {
for (int i = 0; i < k; ++i) {
swap(nums[i + start], nums[n - k + i + start]);
}
n -= k;
start += k;
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/189

Rotate List

https://leetcode.com/problems/rotate-array/

https://leetcode.com/problems/rotate-array/discuss/54277/Summary-of-C%2B%2B-solutions

https://leetcode.com/problems/rotate-array/discuss/54438/My-c%2B%2B-solution-o(n)time-andand-o(1)space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation