把列表右侧N位数移动到左侧的算法实现解析

原创 码农  2020-02-07 12:42:47  阅读 63 次 评论 0 条

给定一个非空列表和一个非负整数 k,把列表右侧的 k 位依次移动到左侧。例如:[1, 2, 3, 4, 5, 6],n 为3,则移动以后,变为:[4, 5, 6, 1, 2, 3]

这道题看起来非常简单,几行代码就能解决:

def shift(target_list, k):
    for i in range(k):
        target_list.insert(0, target_list.pop())

其中,列表的.pop()方法每次可以从列表中返回并删除最右侧的一个元素。再使用.insert()把弹出的这个数插入到列表的最左侧。

但这样做有一个问题——虽然.pop()的时间复杂度为 O(1),但是.insert()的时间复杂度为 O(n)。也就是说,当我在列表最左侧插入一个元素时,列表里面每一个元素都要向右移动 1 位。如果我们要把列表里面右侧 k 个数依次移动到列表左侧,时间复杂度就是O(kn)

那么有没有O(n)时间复杂度的方法呢?当然是有了。

  1. 首先把列表翻转,例如[1, 2, 3, 4, 5, 6]变成[6, 5, 4, 3, 2, 1]。翻转列表的时间复杂度为O(n/2)
  2. 把前k个数翻转:[4, 5, 6, 3, 2, 1]。时间复杂度为O(k/2)
  3. 把第剩下的 n - k个数翻转:[4, 5, 6, 1, 2, 3]。时间复杂度为O((n-k)/2)

整体的时间复杂度为 O(n)

对应的 Python 代码如下:

def swap(target_list, start, end):
    while start < end:
        target_list[start], target_list[end] = target_list[end], target_list[start]
        start += 1
        end -= 1

def shift(target_list, k):
    length = len(target_list)
    k = k % length
    swap(target_list, 0, length - 1)
    swap(target_list, 0, k - 1)
    swap(target_list, k, length - 1)

如果 k 大于列表长度,相当于转了一圈又从头开始,所以真正需要移动的举例为列表长度对 k 求余数。

运行效果如下图所示:

把列表右侧N位数移动到左侧的算法实现解析 把列表右侧N位数移动到左侧的算法实现解析 编程代码
本文地址:https://www.itcodeit.com/post/70.html
版权声明:本文为原创文章,版权归 码农 所有,欢迎分享本文,转载请保留出处!

发表评论


表情

还没有留言,还不快点抢沙发?