Python3实现旋转数组的3种算法

发布时间:2019-10-17 09:07:25编辑:auto阅读(172)

    下面是python3实现的旋转数组的3种算法。
    一、题目
    给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。
    例如:
    输入: [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]
    说明:
    1.尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    2.要求使用空间复杂度为 O(1) 的原地算法。
    二,解题算法
    解法一
    以倒数第 k 个值为分界线,把 nums 截成两组再组合。因为 k 可能大于 nums 的长度(当这两者相等的时候,就相当于 nums 没有移动),所以我们取 k % len(nums),k 和 nums 的长度取余,就是最终我们需要移动的位置
    代码如下:
    if nums:
      k = k % len(nums)
      nums[:]=nums[-k:]+nums[:-k]
    时间:64ms
    假设:
    nums= [1,2,3,4,5,6,7]
    k =3
    运行结果:
    [5, 6, 7, 1, 2, 3, 4]
    解法二
    先把 nums 最后一位移动到第一位,然后删除最后一位,循环k次。k = k % len(nums) ,取余
    代码如下:
    if nums:
      k = k % len(nums)
      while k > 0:
        k -= 1
        nums.insert(0, nums[-1])
        nums.pop()
    时间:172ms
    假设:
    nums= [1,2,3,4,5,6,7]
    k =3
    运行结果:
    [5, 6, 7, 1, 2, 3, 4]
    解法三:
    先把 nums 复制到 old_nums ,然后 nums 中索引为 x 的元素移动 k 个位置后,当前索引为 x+k,其值为 old_nums[x]。,所以我们把 x+k 处理成 (x+k)%len(nums),取余操作,减少重复的次数。
    代码如下:
    if nums:
      old_nums = nums[:]
      l = len(nums)
      for x in range(l):
        nums[(x+k) % l] = old_nums[x]
    时间:64ms
    假设:
    nums= [1,2,3,4,5,6,7]
    k =3
    运行结果:
    [5, 6, 7, 1, 2, 3, 4]

关键字