189. 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].

意为：给出一个数组array，给出一个步数k，让这个数组往前走k步，k可以大于len(array)，那就意味着走过了一圈了，得到最后走完k步的数组。

注：给出的Note是你能否在O(1)的空间复杂度内完成

思路：

后面再来考虑这个note，先完成了再说 1.为了我们不重复走，就将k = k % len(array)，只走需要走的步数 2.我们要移动的是len(array) - k为下标起始的元素到最后一个元素，将这一部分元素放到开头即可

假设array = [1,2,3,4,5,6,7] ，k = 3 1.k = k % len(array) = 3 % 7 = 3 2.走3步，那就是后面3个元素移动到前面，len(array) - k = 4 ，从下标4开始，我们可以把前面的[0,4)4个元素放到array的末尾，也就成了[1,2,3,4,5,6,7,1,2,3,4] 3.将从下标4开始的元素到最末尾，赋值给nums，nums删掉多余的元素

C++—1

class Solution { //runtime=24ms public: void rotate(vector<int>& nums, int k) { int myk = k%nums.size(); int size = nums.size(); for(int i = 0;i < size - myk;i++){ nums.push_back(nums[i]); } for(int i = 0;i < size;i++){ nums[i] = nums[size - myk + i]; } for(int i = 0;i < size - myk;i++){ nums.pop_back(); } } };

python—1

这里用python特别简单，因为python自带一个reverse函数

class Solution(object): def rotate(self, nums, k): #runtime = 80ms k %= len(nums) nums.reverse() temp1 = nums[:k] temp2 = nums[k:] temp2.reverse() temp1.reverse() temp = temp1 + temp2 for i in range(len(nums)): nums[i] = temp[i]

注意一点：reverse函数返回值是None，相当于void，只执行一个操作，将list中的元素逆转。 这样元素的状态是如下变化的：

[1,2,3,4,5,6,7] k = 3 first = [7,6,5,4,3,2,1] second = [5,6,7,4,3,2,1] third = [5,6,7,1,2,3,4]

python—2

python还有一种更简单的做法，也是因为list的强大：

class Solution(object): def rotate(self, nums, k): #runtime = 136ms temp = nums[len(nums)-k:]+nums[:len(nums)-k] for i in range(len(nums)): nums[i] = temp[i]

注：这里为什么k不取k%len(array)，是因为python下list会自动识别某个数的相对位置（如-1表示最后以为，-2表示倒数第二位，依次类推，1表示第一位，len(array) - k 定位就不会出错），不像c++中规定得特别严苛，容易越界。

C++—2.最后来考虑O(1) 空间复杂度的做法了

经过上面的过程，我们可以想到不如用c++封装一个reverse函数，来对原数组进行反转，k = k % len(array)，这样就是O(1)的空间复杂度了。

class Solution { //runtime = 24ms public: void rotate(vector<int>& nums, int k) { int myk = k%nums.size(); reverse(nums, 0, nums.size() - 1); reverse(nums, 0, myk - 1); reverse(nums, myk, nums.size() - 1); } void reverse(vector<int>& nums,int m,int n){ while (m < n) { int temp = nums[m]; nums[m++] = nums[n]; nums[n--] = temp; } } };