V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
ddzzhen
V2EX  ›  Python

各位大佬,请教一下领扣的超出时间限制-python3-第 167 题-两数相加

  •  
  •   ddzzhen · 2018-09-21 15:27:42 +08:00 · 7428 次点击
    这是一个创建于 2240 天前的主题,其中的信息可能已经有所发展或是发生改变。

    小弟是个新手,只会写简单的代码实现结果,对于语法的复杂度没有太多概念,使用以下链接完成领扣第 167 题时,提交代码验证到最后一步 16/17,提示:超出时间限制,感觉可能是遍历列表太多次了,但是如何知道每一步的时间复杂度到底有多大呢?

    https://leetcode-cn.com/playground/TThPBRka

    27 条回复    2018-09-22 11:22:32 +08:00
    Raisu
        1
    Raisu  
       2018-09-21 15:54:01 +08:00
    l , r = 0, len(numbers) -1
    while numbers[l] + numbers[r] != target:
    if numbers[l] + numbers[r] > target:
    r -= 1;
    else:
    l += 1
    return [l+1, r+1]
    youngitachi
        2
    youngitachi  
       2018-09-21 16:08:16 +08:00
    原本最简单(但是不完全靠谱)的方法就是看有几层 for 循环,但是你调用库函数却遮盖了你对复杂度的分析。

    想想看 index 函数的复杂度哈,虽然没去看源码,但是这个查找应该还是去顺序遍历的,也就是说,相当于还是要用一个 for 循环去遍历的,故实际上是两层 for 循环的复杂度,O(N^2)咯。

    这题有 O(N)的解法,次一点,你在查找的时候写个二分查找,也可以到 O(N log(N)),一楼的写法就是 O(N)的,可以好好体会一下(先自己想想解法吧)。
    d18
        3
    d18  
       2018-09-21 16:15:47 +08:00
    同学,刷题就不要用 python 了,和作弊有什么区别。
    像这句“ if sec_num in numbers:”,就是遍历了一遍列表,不超时就怪了。
    LadyChunsKite
        4
    LadyChunsKite  
       2018-09-21 16:28:28 +08:00
    @d18 刷题用 python 怎么就作弊了?算法题和语言有什么关系?
    menc
        5
    menc  
       2018-09-21 16:42:10 +08:00
    @LadyChunsKite
    有关系,不好算时间复杂度。
    if element in list:
    blabla

    这句话看起来像一句话,实际上是 O(n)的时间复杂度。

    python 内置 sort 好用的一比,还内置了 itertools 这些东西,实现全排列和笛卡尔积都是一句话的事。
    可是你知道它们时间复杂度是多少么?
    如果题目考察的就是全排列的实现,你用 itertools 又有什么意义。

    所以如果一定要用 python,建议写成 C 那样原始的形式,但是这样一定有人说“不优雅 /不 pythonic/python 内置了干嘛不用”。
    那就别用 python 了,统一用 c/cpp 吧。
    sagaxu
        6
    sagaxu  
       2018-09-21 16:50:26 +08:00 via Android
    @menc 用了 python 就不会算复杂度?那只能说明不会用 python
    menc
        7
    menc  
       2018-09-21 17:01:58 +08:00
    @sagaxu
    来说下 python sort 的时间复杂度
    说下 python permutation 的时间复杂度
    menc
        8
    menc  
       2018-09-21 17:04:06 +08:00
    @sagaxu
    90%的人说不出 python sort 的实现,
    大多数人说个 nlgn 也只是基于当前一般 sort 的实现方法说的。
    liprais
        9
    liprais  
       2018-09-21 17:11:54 +08:00
    https://www.v2ex.com/t/382458#reply59
    v2ex 有一点好处就是不能删帖
    stevenbipt
        10
    stevenbipt  
       2018-09-21 17:15:43 +08:00 via Android
    Python 太慢了,更得考虑时间复杂度问题了,C/C++和 java 速度相对快上不少,n²复杂度应该都不会出线超时,但是 Python 不好说
    LadyChunsKite
        11
    LadyChunsKite  
       2018-09-21 17:17:21 +08:00
    @menc 我觉得这不是 python 的问题,而是写代码的人的问题。一些 easy 题确实用一些 pythonic 的代码很轻松就解决了。但是我觉得,随着问题难度的上升,不是靠几个 sort,几个 in 就能解决的。

    就拿这题来说:
    https://leetcode.com/problems/boats-to-save-people/description/
    要用到排序,但我觉得没必要把排序算法写一遍,考察的重点不是排序。
    lance6716
        12
    lance6716  
       2018-09-21 17:17:34 +08:00 via Android
    @liprais 北航挺好啊,我们小破邮瑟瑟发抖
    另外 Cpython 像我这种非 CS 专业的都能看懂,其实并不算很刁钻的要求…
    sagaxu
        13
    sagaxu  
       2018-09-21 17:21:22 +08:00 via Android
    @menc sort 在 python 中的复杂度,跟 cpp 的或者 java 的不应该有数量级上的差异。除非自己手动 sort,否则任何语言的 sort 库都会面临 python 一样的问题。

    排列组合库,时间复杂度可以认为是结果条数乘以每条长度。主流实现都应该大差不差。
    ylsc633
        14
    ylsc633  
       2018-09-21 17:23:27 +08:00
    没用 python 解过

    很多题目限制 时间和空间复杂度, 偶尔还要原地!

    你们用内置函数的 怎么计算这些啊?
    lance6716
        15
    lance6716  
       2018-09-21 17:33:03 +08:00
    @sagaxu 这个回答的意思就是,你属于 90%
    ddzzhen
        16
    ddzzhen  
    OP
       2018-09-21 18:55:12 +08:00 via Android
    @Raisu 高手
    ddzzhen
        17
    ddzzhen  
    OP
       2018-09-21 18:56:16 +08:00 via Android
    @d18 哎,才疏学浅
    ddzzhen
        18
    ddzzhen  
    OP
       2018-09-21 18:58:41 +08:00 via Android
    @ylsc633 高手,主要是想练习一下 python,奈何逻辑完整了之后还要看复杂度,心塞
    loryyang
        19
    loryyang  
       2018-09-21 19:17:27 +08:00
    不是,这题就是故意卡你这种解法的,你这种暴力的方法肯定会被 judge 卡成 TLE 的。。
    至于分析时间复杂度,这个你去学学呗,不难的
    Raisu
        20
    Raisu  
       2018-09-21 19:34:32 +08:00
    dic = {}
    for i in range(len(numbers)):

    if numbers[i] in dic:
    if target - numbers[i] == numbers[i]:
    return [dic[numbers[i]].pop(), i + 1]
    else:
    dic[numbers[i]] = [i + 1]
    for k in dic:
    if target - k in dic:
    if dic[k][0] < dic[target - k][0]:
    return [dic[k][0], dic[target - k][0]]
    else:
    return [dic[target - k][0], dic[k][0]]


    讨论组里面用字典的解法,可以通过,原因是字典的检索速度会比较快一点。。。
    Raisu
        21
    Raisu  
       2018-09-21 19:36:15 +08:00
    我也是新手啊。。。自学转开发才半年,
    Raisu
        22
    Raisu  
       2018-09-21 19:54:01 +08:00
    试了一下,用 set 过滤了一下也能通过。。。。不过有点取巧就是了。代码怎么带格式?
    l = len(numbers)
    a = target // 2
    if a in numbers:
    index = numbers.index(a)
    if a in numbers[index + 1:]:
    return [index+1, index + 2]
    n = list(set(numbers))
    for i in range(len(n)):
    ans = target - n[i]
    if ans in n:
    index2 = numbers.index(ans)
    index1 = numbers.index(n[i])
    return sorted([index1 + 1, index2 + 1])
    ddzzhen
        23
    ddzzhen  
    OP
       2018-09-21 23:05:43 +08:00
    @loryyang 多谢高手,确实学了 python 感觉效率是个瓶颈
    ddzzhen
        24
    ddzzhen  
    OP
       2018-09-21 23:06:15 +08:00
    @Raisu 多谢,当时解题的时候考虑过这个,但是没有实施
    vancoder
        25
    vancoder  
       2018-09-22 02:14:11 +08:00
    这不是 python 效率的问题,是你的解法时间复杂度的问题,建议学习一下如何分析算法时间复杂度
    widewing
        26
    widewing  
       2018-09-22 08:39:32 +08:00 via Android
    没搞错吧楼上的各位,哪个语言没有个内置的 sort?莫非你们都用汇编的?
    cyrbuzz
        27
    cyrbuzz  
       2018-09-22 11:22:32 +08:00   ❤️ 1
    代码里有 print,把 print 去掉吧...

    in 这种语句尽量用 set 代替 list 吧。list 执行是 O(n) ,set 是 O (1)。

    这个题应该是想让你用 O(n) 的解法来解,否则不会又出来一个标明 已排过序 的在用 未排过序 时的解法再解一次吧...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   980 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 22:13 · PVG 06:13 · LAX 14:13 · JFK 17:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.