题目：
用额外数组的方式。这种方法时间复杂度在 O(n)，但是开辟额外数组也会花时间空间复杂度也是 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <vector>
using std::vector;
class Solution {
public:
void rotate(vector<int> &nums, int k) {
int n;
int tmp;
int pos;
n = nums.size();
vector<int> vec(n);
for (int i = 0; i < n; i++) {
pos = (i + k) % n;
vec[pos] = nums[i];
}
nums = std::move(vec);
}
};
|
另一种巧妙的方式：
我们将数组的元素向右移动 k 次后，尾部k mod n个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的k mod n个元素就被移至数组头部，然后我们再翻转 [0,k mod n−1] 区间的元素和 [k mod n,n−1] 区间的元素即能得到最后的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <algorithm>
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
std::reverse(nums.begin(), nums.begin() + n - k);
std::reverse(nums.begin() + n - k, nums.end());
std::reverse(nums.begin(), nums.end());
}
};
|
leetcode hot 100 rewrite
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <vector>
#include <algorithm>
using std::vector;
class Solution {
public:
void rotate(vector<int> &nums, int k)
{
int n = nums.size();
k = k % n;
std::reverse(nums.begin(), nums.begin() + n - k);
std::reverse(nums.begin() + n - k, nums.end());
std::reverse(nums.begin(), nums.end());
}
};
|
