Rotate Array

Description：

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.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

Code：

1.解法1：直接映射

时间复杂度O(N), 空间复杂度O(N)

 1 void rotate(int nums[], int n, int k) {
 2         //算法1：直接映射
 3         int *p = new int[n];
 4         for (int i = 0; i < n; i++)
 5             p[i] = nums[i];
 6             
 7         for (int i = 0; i < n; i++)
 8         {
 9           nums[(i+k)%n] = p[i];
10         }
11         delete []p;
12     }

2.解法2：每次移动一步，共循环k次，时间复杂度O(KN)，空间复杂度O(1)

 void rotate(int nums[], int n, int k) {
      for (int i = 0; i < k%n; ++i)
     {
             int temp = nums[n-1];
             for (int j = n-1; j > 0; --j)
           {
                  nums[j] = nums[j-1];
           }
           nums[0] = temp;
     }
    }

3.解法3，类似于位反序