# C++实现LeetCode(189.旋转数组)

[LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative.

## [LeetCode] 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]

No编程客栈te:

• 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?

```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;
}
}
};```