问题：给定一个数组，将数组中的元素向右移动?k?个位置，其中?k?是非负数。
要求：空间复杂度为?O(1)。
其中：1 <= nums.length <= 2 * 104
???-2^31?<= nums[i] <= 2^31?- 1
???0 <= k <= 10^5
示例：
???输入：nums = [-1,-100,3,99], k = 2
???输出：[3,99,-1,-100]
分析：由于要求空间复杂度为?O(1)，所以不能使用临时数组。
解答：显然，应先求得kk = k % nums.length。
????????1、多次反转
? ? ? ? ? ? ? ? 先反转全部数组，接着反转前kk个，然后反转剩下的。
? ? ? ? ?代码如下：
class solution
{
public:
void rotate(vector<int>& nums, int k)
{
if (nums.size() <= 1)
return;
int kk = k % nums.size();
if (kk == 0)
return;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k + 1);
reverse(nums.begin() + k + 1, nums.end());
}
};? ? ? ? 2、环形旋转
? ? ? ? ? ? ? ? 把数组看成是环形的，每一个数字都顺时针移动kk位。
????????????????
?
循环nums.length次后，数组便完成旋转。
但是，这里需注意一点，就是当nums.length % kk == 0时，移动的数字会原地打转。
?所以，我们可以先求得l = nums.length / k，然后分为k次循环，每次循环都将l个元素移动k位，如图。
?
?
?代码如下：
class Solution {
public:
void rotate(vector<int>& nums, int k)
{
if (nums.size() <= 1)
return;
int kk = k % nums.size();
if (kk == 0)
return;
if (nums.size() % kk)
{
int hold = nums[0], index = 0;
for (int i = 0; i < nums.size(); i++)
{
index = (index + kk) % nums.size();
swap(hold, nums[index]);
}
}
else
{
int l = nums.size() / k;
for (int i = 0; i < kk; i++)
{
int hold = nums[i], index = i;
for (int j = 0; j < l; j++)
{
index = (index + kk) % nums.size();
swap(hold, nums[index]);
}
}
}
}
};