leetcode Rotate Array

题目链接：Rotate Array

题目描述(Description)

Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

翻译

旋转数组

旋转一个含有n个元素的数组，把它向右移k位。

例如，n=7,k=3，数组[1,2,3,4,5,6,7]旋转后结果为[5,6,7,1,2,3,4]。

注意：

尽可能多的提出你的想法，至少有三种解决办法。

分析

方法1（时间复杂度O(n))

不管是数组还是字符串，只要是把两个相同的数组和字符串连在一起，就包含了所有的旋转结果。

比如：a:1-2-3-4-5-6-7,两个a相连：b:1-2-3-4-5-6-7-1-2-3-4-5-6-7，所有a旋转的结果都是b的子集。

在这个题目中，有了前面的铺垫，我们可以声明一个数组变量rotate，使其长度是给定数组长度的两倍，然后复制原数组两次。根据给定的k,算出旋转之后的数组第一个元素在rotate中的位置，然后把之后的n个元素赋值到原数组里即可。

• 如何找旋转后数组的第一个位置？

  假设nums[]={1,2,3,4,5,6,7},n=7,k=3,rotate[]={1,2,3,4,5,6,7,1,2,3,4,5,6,7},旋转后的第一个元素是5（rotate[4]),4恰好是7-3即(n-k)。

• 如果k的值大于7怎么办？

  对于旋转操作，其本身具有循环性，相当于转了k/n个圈，又回到了k%n的地方。所以在上述的分析中，所有跟k有关的地方都要换成k%n。

这只是一种方法，还有其他方法？容我想想……

代码

void rotate(int nums[], int n, int k) {
        if(k%n==0)
            return;
        int *rotate=(int *)malloc(sizeof(int)*(2*n+1));
        for(int i=0;i<2*n;i++)
            rotate[i]=nums[i%n];
        for(int j=0;j<n;j++)
            nums[j]=rotate[n-k%n+j];
}