LeetCode使用Python实现旋转数组

需求：

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例1：

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]  

示例2：

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]  

说明：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的原地算法。

废话少说直接上代码：

class Solution:
	def rotate(self, nums, k):
	"""
	:type nums: List[int]
	:type k: int
	:rtype: void Do not return anything, modify nums in-place instead.
	"""
	# 法一：  
	# l = len(nums)
	# k = k % l  
	# nums[:] = nums[l-k:] + nums[:l-k]  

	# 法二：  
	# l = len(nums)
	# k = k % l  
	# nums[:l-k] = reversed(nums[:l-k])  
	# nums[l-k:] = reversed(nums[l-k:])
	# nums[:] = reversed(nums)  
	
	# 法三：  
	def rev(start, end, nums):  
		while start < end:  
			nums[start], nums[end] = nums[end], nums[start]
			start += 1
			end -= 1

	l = len(nums)
	k = k % l  
	rev(0, l-k-1, nums)
	rev(l-k, l-1, nums)
	rev(0, l-1, nums)  

总结：

第一种方法是直接将原数组做切片处理，然后原地拼接。

第二种方法是使用Python内置函数reversed将数组进行反转，根据旋转数组的特点，我们可以事先对元素组的切片部分分别进行反转，最后对整个数组进行反转，即可达到翻转的效果。

第三种方法实际上与第二种方法异曲同工，第二种方法的Python内置函数reversed有返回值，并不是在原数组上进行操作，在第三种方法中，我们自己实现了反转功能的函数rev，这样我们可以直接原地进行数组的反转。