专栏首页未闻Code算法题:把列表右侧 k 位数依次移动到左侧

算法题:把列表右侧 k 位数依次移动到左侧

给定一个非空列表和一个非负整数 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 求余数。

运行效果如下图所示:

本文分享自微信公众号 - 未闻Code(itskingname),作者:kingname

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一日一技:如何更好地理解归并排序?

    在昨天的文章里面,我们已经知道,可以使用 heapq.merge把两个有序列表合并成新的有序列表。

    青南
  • 一日一技:使用十根手指数出1024个数

    正常情况下人有十根手指,所以一共可以计数1024个,但是一般在计数到第4个数的时候你就会挨打。明白二进制的自然知道我说的是什么意思。不明白二进制的,请看下面的动...

    青南
  • 在MongoDB中使用聚合操作筛选与修改字段

    “$match”可以筛选出需要的记录,那么如果想只返回部分字段,又应该怎么做呢?这时就需要使用关键字“$project”。

    青南
  • 手把手教你使用sklearn快速入门机器学习

    sklearn(scikit-learn)是一个非常优秀的Python库,它封装了机器学习中常用的算法,包括监督学习、非监督学习等。它有以下几个特点:

    abs_zero
  • Centos7笔记 | 操作系统启动流程、Linux用户及权限

    Centos 服务管理器:systemd和init并行运行。(systemctl和service)

    网络技术联盟站
  • 人工智能帮助预测混合用药的副作用

    斯坦福大学的科研人员设计出了一种卷积神经网络,能够预测混合使用多种药物可能产生的副作用。

    人工智能快报
  • 求超大文件上传方案( SpringMVC )

    众所皆知,web上传大文件,一直是一个痛。上传文件大小限制,页面响应时间超时.这些都是web开发所必须直面的。

    用户6892318
  • 硬核还原:显微镜手撸晶体管,逆向工程还原经典计算器

    它很受欢迎,自1974年发售,就频频出现在《大众机械》等出版物封面。其巧妙编写的固件,使它本只用于基础算术的处理器,能马力倍开远远超出正常性能。这也使得Sinc...

    大数据文摘
  • 玖富获1.1亿美元融资,互联网金融的好时代?

    余额宝面世之后,互联网金融市场被高度关注,持续发酵。互联网理财、P2P借贷、个人征信、网络银行、分期、众筹,每一个细分领域都在上演着激烈的竞争。不过两年下来却没...

    罗超频道
  • Makefile文件编写

    make 的参数有很多, 可以通过 make -h 去查看, 下面只介绍几个我认为比较有用的。

    用户2929716

扫码关注云+社区

领取腾讯云代金券