LeetCode#189 Rotate Array

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]=rear
10         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<end:
 5         nums[start],nums[end]=nums[end],nums[start]
 6         start+=1
 7         end-=1
 8 
 9 def rotate(nums, k):
10     n=len(nums)
11     k=k%n
12     reverse(nums,0,n-k-1)
13     reverse(nums,n-k,n-1)
14     reverse(nums,0,n-1)