Problem Definition:

　　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.

　　Hint:

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

 

Solution 1：最简单粗暴的，每次右移一个坑，移k次。空间复杂度是O(1)，然并软，超时。

1 def rotate(nums, k): 2     n=len(nums) 3     if n==0: 4         return 5     while k>0: 6         rear=nums[n-1] 7         for i in range(n-1,0,-1): 8             nums[i]=nums[i-1] 9         nums[0]=rear10         k-=1

 

Solution 2: 动用一个临时数组来存放数组前面一部分，空间复杂度 O(n-k)。

1 def rotate(self, nums, k):2     n=len(nums)3     k=k%n   #一点优化,含n个数的数组，移动n次相当于没移动4     nums[:k],nums[k:]=nums[n-k:n],nums[:n-k]

 

Solution 3 (硬菜)： 不需要临时数组，空间复杂度O(1)，三次反转。

　　一个栗子: nums=[1,2,3,4,5]　　k=2

　　　　　　  [1,2,3,  |  4,5]  --> 

　　　　　　　　　　　　　　　　　　[3,2,1  |  4,5]  --> 

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　[3,2,1  |  5,4]  -->

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　[4,5,1,2,3]

1 #辅助函数，将数组nums中下标start到end的子数组反转 2 def reverse(nums,start,end): 3     # space O(1) 4     while start