[LeetCode] 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.

[show hint]

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

解法1：1.旋转整个数组： [1,2,3,4,5,6,7] => [7,6,5,4,3,2,1]

　　　 2.旋转前k个数：[7,6,5,4,3,2,1] => [5,6,7,4,3,2,1]

　　　 3.旋转后n-k个数：[5,6,7,4,3,2,1] => [5,6,7,1,2,3,4]

　　　　时间复杂度O(n), 空间复杂度O(1)

 1 class Solution {
 2 public:
 3     void rotate(int nums[], int n, int k) {
 4         if (nums == NULL || n <= 0 || k <= 0)
 5             return;
 6          k %= n;
 7         reverse(nums, 0, n - 1);
 8         reverse(nums, 0, k - 1);
 9         reverse(nums, k, n - 1);
10     }
11     
12     void reverse(int nums[], int begin, int end) {
13         if (begin >= end) return;
14         while (begin < end) {
15             swap(nums[begin++], nums[end--]);
16         }
17     }
18 };

解法2：参考https://oj.leetcode.com/discuss/26088/solutions-with-extra-memory-dont-know-the-third-one-yet-idea的answer
　　

 1 class Solution {
 2 public:
 3     void rotate(int nums[], int n, int k) {
 4         if (nums == NULL || n <=0 || k <= 0)
 5             return;
 6         k %= n;
 7         int index = 0;
 8         int cycle = 0;
 9         int next = 0;
10         int temp = nums[next];
11         for (int i = 0; i < n; ++i) {
12             next = (next + k) % n;
13             swap(nums[next], temp);
14             if (cycle == next) {
15                 next++;
16                 cycle = next;
17                 temp = nums[next];
18             }
19         }
20     }
21 };

更多解法:https://leetcode.com/discuss/27387/summary-of-c-solutions