1 题目
2 思路
题目要求想出尽可能多的解决方案。
2.1 首先想到，开辟k个空间将最右边k个数存下来，数组右移k个位置，再将存下来的k个数放在数组的开头。时间复杂度：O(n)， 空间复杂度为 O(n)。
2.2 暴力解法（不要使用暴力，使用暴力是在证明自己头脑简单），循环右移，每次移动一格，移动k次。时间复杂度：O(n2)， 空间复杂度为 O(1)。
没想到时间复杂度O(n)，空间复杂度O(1)的方法，直接看题解。
3 题解
3.1 使用额外数组
官方题解直接申请了与原数组同样大小的数组，而不是k个元素的数组。从时间复杂度和空间复杂度上看，两者相同。前者代码更清晰，后者代码比较琐碎。通常只考虑时间复杂度和空间复杂度，但是在生产环境中，有时也要根据实际情况考虑用更少的空间，更少的时间（例如时间复杂度n 比2n，从系数上看就要好一些）。
时间复杂度：O(n)，空间复杂度：O(n)。
申请与原数组同样大小的数组：
将原数组位置i的元素，放进新数组的 (i+k)%n 的位置。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> nums_tmp(n);
for (int i = 0; i < n; ++i) {
nums_tmp[(i + k) % n] = nums[i];
}
nums.assign(nums_tmp.begin(), nums_tmp.end());
}
};申请k大小的数组：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> nums_k(k);
for (int i = n - k, j = 0; j < k;) {
nums_k[j++] = nums[i++];
}
for (int i = n - 1, j = n - k - 1; j >= 0;) {
nums[i--] = nums[j--];
}
for (int i = 0, j = 0; i < k;) {
nums[i++] = nums_k[j++];
}
}
};这个解法只能通过部分测试用例，这是为什么呢？这是因为这个解法只考虑轮转的k <= n，并没有考虑k > n的情况。所以开辟k大小的数组是行不通的。但是！可以预处理k，使得 k = k % n，这样就ok了。
// 申请k大小的数组（k = k % n）
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
vector<int> nums_k(k);
for (int i = n - k, j = 0; j < k;) {
nums_k[j++] = nums[i++];
}
for (int i = n - 1, j = n - k - 1; j >= 0;) {
nums[i--] = nums[j--];
}
for (int i = 0, j = 0; i < k;) {
nums[i++] = nums_k[j++];
}
}
};3.2 环状替换
这个方法较难理解，需要细细琢磨。
方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置，这样被放置位置的元素会被覆盖从而丢失。因此，从另一个角度，我们可以将被替换的元素保存在变量 temp 中，从而避免了额外数组的开销。
我们从位置 0 开始，最初令 temp=nums[0]。根据规则，位置 0 的元素会放至 (0+k)modn 的位置，令 x=(0+k)modn，此时交换 temp 和 nums[x]，完成位置 x 的更新。然后，我们考察位置 x，并交换 temp 和 nums[(x+k)modn]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。
容易发现，当回到初始位置 0 时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从 0 开始不断遍历，最终回到起点 0 的过程中，我们遍历了多少个元素？
由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；再设该过程总共遍历了 b 个元素。因此，我们有 an=bk，即 an 一定为 n,k 的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 an 就是 n,k 的最小公倍数 lcm(n,k)，因此 b 就为 lcm(n,k)/k。
这说明单次遍历会访问到 lcm(n,k)/k 个元素。为了访问到所有的元素，我们需要进行遍历的次数为 n/(lcm(n,k)/k) = nk/lcm(n,k) = gcd(n,k)，其中 gcd 指的是最大公约数。
总之，从一个起点开始到回到该起点，为一次遍历，遍历的次数为gcd(n,k)。
时间复杂度：O(n)，空间复杂度：O(1)。
// 环状替换
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
int count = gcd(n, k);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[current];
do {
int next = (current + k) % n;
swap(nums[next], prev);
current = next;
} while (start != current);
}
}
};3.3 数组翻转
优雅的解决方法，非常容易理解。
数组后k个元素移动到了前k个，前n-k个元素移动到了后n-k个。可以先将整个数组翻转，然后翻转前k个元素，再翻转前k个元素，再翻转后n-k个元素。注意这里的k都需要mod n。
时间复杂度：O(2n) = O(n)，空间复杂度：O(1)。
// 数组翻转
class Solution {
public:
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
++start;
--end;
}
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
};4 vector的用法积累
在3.1小节中，代码中使用了 vector<int> nums_tmp(n); ，这里有值得注意的地方，主要讨论size和capacity。
int n = 5;
vector<int> nums(n);
cout << nums.size();
cout << nums.capacity();size()表示当前vector中实际存储的元素个数。
capacity()表示当前vector在不重新分配内存的情况下，最多可以容纳多少元素。
4.1 vector<int> nums(n)
int n = 5;
vector<int> nums(n); // 创建一个长度为5的int类型的vector，初始值为0
// size = 5, capacity >= 5nums(n)默认初始化为0，nums(n, 2)则显式初始化为2。
4.2 resize()
int n = 5;
vector<int> nums; // 空的vector，size = 0, capacity >= 0
nums.resize(n); // size = 5, capacity >= 5nums.resize(n)默认初始化为0，nums.resize(n, 2)则显式初始化为2。
4.3 reserve()
vector<int> nums; // size = 0, capacity >= 0
nums.reserve(100); // size = 0, capacity >= 100当插入元素时（比如push_back），如果size超过capacity，vector会自动扩容，自动分配更大的内存。
size永远不会超过capacity。
resize(n)会改变size，如果n大于当前的capacity，会自动扩容。
reserve(n)只改变capacity，不改变size。
注意，只能访问下标为 0~nums.size()-1的元素。
评论区