[LeetCode 189] 轮转数组
题目描述：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
范围：
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
105
1 \le nums.length \le 105
1≤nums.length≤105
−
2
31
≤
n
u
m
s
[
i
]
≤
2
31
−
1
-2^{31} \le nums[i] \le 2^{31} - 1
−231≤nums[i]≤231−1
0
≤
k
≤
1
0
5
0 \le k \le 10^5
0≤k≤105
思路：
1. 暴力new数组存储
void rotate(vector<int>& nums, int k) {
size_tn = nums.size();
vector<int> temp(n, 0);
for(size_t i = 0; i < nums.size(); ++ i)
temp[(i + k) % n] = nums[i];
nums = temp;
return ;
}
2. 数组翻转 & 双指针
这边双指针指的是如果要自己写 r e v e r s e reverse reverse 的话。
（思路copy官方题解，but 王道考研里遇到过，很简单的逻辑）
该方法基于如下的事实：当我们将数组的元素向右移动
k
k
k 次后，尾部
k
m
o
d
n
k\ mod\ n
k mod n 个元素会移动至数组头部，其余元素向后移动
k
m
o
d
n
k\ mod\ n
k mod n 个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的
k
m
o
d
n
k\ mod\ n
k mod n 个元素就被移至数组头部，然后我们再翻转
[
0
,
k
m
o
d
n
−
1
]
[0,k\ mod\ n−1]
[0,k mod n−1] 区间的元素和
[
k
m
o
d
n
,
n
−
1
]
[k\ mod\ n,n−1]
[k mod n,n−1] 区间的元素即能得到最后的答案。
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) {
k %= nums.size();
Reverse(nums, 0, nums.size() - 1);
Reverse(nums, 0, k - 1);
Reverse(nums, k, nums.size() - 1);
/**
or use stl reverse
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums,end());
**/
}
3. 原地轮转替换
最优但不好理解，umm maybe尝试群论/数论可以理解
（退步太多，思维缓慢，重新刷题，勉励自己）
两篇文章可帮助理解：blog 1，blog 2
void rotate(vector<int>& nums, int k) {
k %= nums.size();
int n = nums.size();
int cnt = gcd(n, k);
for(int i = 0; i < cnt; ++ i) {
int j = i;
int pre = nums[i];
do{
int ne = (j + k) % n;
swap(nums[ne], pre);
j = ne;
} while(i != j);
}
}