189. 旋转数组

文|Seraph

1 问题

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]>
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

2 解题

初解：

思路：

void swap(int &a, int &b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int iSize = nums.size();
        if(iSize==0 || k%iSize==0)
        {
            return;
        }
        int iDistance = k%iSize;
        int m=iDistance;
        int n=0;
        for(int i=1;i<iSize;i++)
        {
            if(n==m)
            {
                n++;
                i++;
                m=n+iDistance;
            }
            swap(nums[n],nums[m]);
            m+=iDistance;
            m%=iSize;          
        }
    }
};

结果：
改进1：

终解：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(nums.empty()||(k%=nums.size())==0||nums.size()==1)
            return;
        int len = nums.size();
        reverse(nums.begin(),nums.begin()+len-k);
        reverse(nums.begin()+len-k,nums.end());
        reverse(nums.begin(),nums.end());
    }
};

3 积累知识点