LeetCode 189：旋转数组[初级]

题目

189：旋转数组
给定一个数组，将数组中的元素向右移动 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) 的原地算法。

分析

• 方法一:空间复杂度O(n)
  首先想到的就是切片，以[-1,-100,3,99]，k=2 为例： 先用[-2:]拿到 [3,99]，再用[:-2]得到剩下的[-1,-100]

def rotate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    nums = nums[-k:] + nums[:-k]

提交以后才发现结果不对，这才想起nums此时其实是一个新建的局部变量，不影响原来的List，修改如下

def rotate(self, nums, k):
    new_nums = nums[-k:] + nums[:-k]
    for i in range(len(nums)):
        nums[i] = new_nums[i]

还是没有考虑全，还有nums=[1,2,3],k=5这种k>len(nums)的情况，我们进行取模运算，最终代码：

def rotate(self, nums, k):
    length = len(nums)
    i = k%length
    new_nums = nums[-i:] + nums[:-i]
    for i in range(len(nums)):
        nums[i] = new_nums[i]

看了别的提交的代码后发现可以用Python浅拷贝的魔法糖list[:],它等价于list.copy()：只复制对象地址，而非完整对象资源。

def rotate(self, nums, k):
    
    i = len(nums) - k 
    nums[:] = nums[i:] + nums[:i]

• 方法2:空间复杂度O(1)
  按题目要求，我们可以用这个思路：删除最后一个元素，把最后一个元素的内容插入到List的开头位置

def rotate(self,nums,k):
    while k:
        tail = nums.pop()
        nums.insert(0,tail)
        k -=1

• 日常使用的话,标准集合库collections里deque(双向列表)提供了旋转数组的方法:rotate

from collections import deque
d = deque([1,2,3,4,6])
d.rotate(3)