189 Rotate Array

题目

189 Rotate Array

题解

拓展阅读：《编程珠玑》中的2.3节有对于这个问题的阐述。

方法一

如果想只用\(O(1)\)的空间解决此问题，就要对元素进行恰当的交换。实现交换本身并不难，使用一个临时变量保存被交换出去的数值，在下一次交换中再把这个数值交换进数组即可。问题的关键是：如何保证输入数组的所有元素都被交换到正确的位置。

如果只从第一个位置出发进行交换的话，并不能保证所有元素都能被交换。一个例子是对数组\([1,2,3,4,5,6]\)进行\(k=3\)的旋转。若从位置\(0\)出发的话只有位置\(\text{0 4 2}\)上的元素会被交换。

为了解决这个问题，我们需要观察元素交换的特征。现在记含有\(n\)个数的数组为\([m_0,m_1,\dots,m_n]\)，旋转位移为\(k\)，并定义某个位置\(i\)上的一轮交换为从位置\(i\)出发开始交换直到回到位置\(i\)。我们可以观察到下列事实：

1. 对于任意一轮交换，都至少有\(\lfloor{n/k} \rfloor\)个不同元素被交换
2. 在位置\(i\)上进行一轮交换时，位于位置开区间\((i, i+k)\)上的元素不会被交换到
3. 对于任意的正整数\(l\)，在位置\((i+lk) \mod n\)上的一轮交换与在位置\(i\)上的效果一样

综合上述事实，我们可以得到一个结论：交换最多只需要进行\(k\)轮，并且这\(k\)轮交换分别从位置\(0,1,\dots,k-1\)上进行。 在一些情况下，交换所需要的轮数会少于\(k\)轮，所以我们需要加一个计数器count来记录当前已交换的元素个数，一旦count等于n则返回数组。

方法二

对于这个问题，还有另一种简便的方法。 观察可知，数组旋转时，最后面的k个元素会移到数组前面，其他的元素会往后移。根据这个事实，我们可以采用分段反转数组的做法来完成数组旋转：

1. 反转整个数组
2. 反转前\(k\)个元素
3. 反转后\(n-k\)个元素

深入思考

1. 模算术与环论
2. 方法二正确性的证明

代码

class Solution
{
  public:
    void rotate(vector<int> &nums, int k)
    {
        int size = nums.size();
        if (size == 1 || k == 0)
        {
            return;
        }

        int offsetAfterCycle = size % k;
        int count = 0;
        for (int start = 0; start < k; start++)
        {
            int move = start;
            int nextMove = 0;
            int previous = nums[move];
            int temp = 0;
            do
            {
                nextMove = (move + k) % size;
                temp = nums[nextMove];
                nums[nextMove] = previous;
                previous = temp;
                move = nextMove;
                count++;
                if (count == size)
                {
                    return;
                }
            } while (move != start);
        }
    }
};