【LeetCode-中等】189. 轮转数组-双指针

189. 轮转数组

题目：
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。


解法一：使用额外的数组
从原数组的第 nums.size()-k 位开始加到答案数组中，然后将原数组的前 nums.size()-k 位加到答案数组中，即为向右轮转 k 位后的结果。
需要注意 k>nums.size() 的情况，例：nums.size()=3，k=4 向右轮转4位的结果与向右轮转1位相同，nums.size()-k 值为负数，需要额外处理。

这里我犯傻了，只要k %= nums.size()就可以了

class Solution {
public:
    void rotate(vector& nums, int k) {
        vector ans;
        int n;
        k %= nums.size();
        n=nums.size()-k;
        
        for(int i=n;i 
以上是我的代码，显得有些繁琐
 力扣对于该解法给出了更为简洁易懂的代码：
 用 n 表示数组的长度，遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置，最后将新数组拷贝至原数组。
 
class Solution {
public:
    void rotate(vector& nums, int k) {
        int n = nums.size();
        vector newArr(n);
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};
 
该解法时间复杂度为O(n)
 
解法二：环状替换
 将被替换的元素保存在变量 temp 中。
 从位置 0 开始，令 temp=nums[0]。根据规则，位置 0 的元素会放至 (0+k) mod n 的位置，令 x=(0+k) mod n，此时交换 temp 和 nums[x]，完成位置 x 的更新。然后，考察位置 x，并交换 temp 和 nums[(x+k)modn]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。
 当回到初始位置 0 时，有些数字可能还没有遍历到，从下一个数字开始重复的过程。使用单独的变量 count 跟踪当前已经访问的元素数量，当 count=n 时，结束遍历过程。
 
 
class Solution {
public:
    void rotate(vector& nums, int k) {
        int n=nums.size();
        k %= n;
        int count=0;
        int start=0;
        while(count 
解法三：数组翻转
 可以先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，然后再翻转 [0,k mod n − 1] 区间的元素和 [k mod n,n−1] 区间的元素即可得到答案。
 例：
 
 
class Solution {
public:
    void reserve(vector& nums,int start,int end){
        while(start<=end){
            swap(nums[start],nums[end]);
            start++;
            end--;
        }
    }
    void rotate(vector& nums, int k) {
        int n=nums.size();
        k %= n;
        reserve(nums,0,n-1);
        reserve(nums,0,k-1);
        reserve(nums,k,n-1);
    }
};