推荐学习书目
› 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
picy
V2EX  ›  Python

python 的 list 效率底下?

  •  
  •   picy · Nov 11, 2014 · 9050 views
    This topic created in 4393 days ago, the information mentioned may be changed or developed.

    题目

    Design a stack that supports push, pop, top, and retrievingthe minimum element in constant time.

    • push(x) – Push element x onto stack.
    • pop() – Removes the element on top of the stack.
    • top() – Get the top element.
    • getMin() – Retrieve the minimum element in the stack.

    答案:

    class MinStack:
        def __init__(self):
            self.L=[]
        def pop(self):
            return self.L.pop()
        def push(self,x):
            self.L.append(x)
        def top(self):
            return self.L[-1]
        def getMin(self):
            tmpL = self.L[:]
            tmpL.sort()
            return tmpL[0]
    

    每次提示答案都超时…表吐槽,表示刚学python

    43 replies  •  2014-11-12 17:01:00 +08:00
    Altynai
    Altynai
    Nov 11, 2014❤️1
    1
    你getMin复杂度都O(nlogn)了,题目说了**constant time**
    takato
    takato
    Nov 11, 2014 via iPhone❤️1
    2
    常数级复杂度,只要额外维持一个最小值就可以了
    bcxx
    bcxx
    Nov 11, 2014
    3
    @takato 不是一个,是最小值的历史记录
    wheatcc
    wheatcc
    Nov 11, 2014
    4
    大力哥好!
    wzzyj8
    wzzyj8
    Nov 11, 2014
    5
    getmin用list改用tuple,至少快10倍。


    bcxx
    bcxx
    Nov 11, 2014
    6
    @wzzyj8 看题……不是 list 本身的问题- -
    staticor
    staticor
    Nov 12, 2014
    7
    另外生成一个最小栈, push时比一下.
    ivanlw
    ivanlw
    Nov 12, 2014❤️1
    8
    好经典的蒂姆
    rwalle
    rwalle
    Nov 12, 2014 via Android
    9
    目测楼主以前没学过编程?经验太少 getMin这么简单的事情用sort就是杀鸡用牛刀
    ryd994
    ryd994
    Nov 12, 2014 via Android
    10
    每次插入都和当前最小比较一下,小于就换
    每次pop就要重新sort了
    ryd994
    ryd994
    Nov 12, 2014 via Android
    11
    pop可能要重新sort
    gt11799
    gt11799
    Nov 12, 2014
    13
    题主是只想实现一个可以取最小值的栈?
    heapq是一个最小堆,内部应该是一个二叉树,父节点始终小于子节点,因此顶点是最小的数。每当取出一个值,则两个子节点对比,小的上升。(实际上不是如此,不过这样容易理解)
    可以先使用heapq把这个类实现了,然后试试看,自己能不能写一个最小堆?
    msg7086
    msg7086
    Nov 12, 2014❤️1
    14
    @gt11799
    我看题目里的要求,应该不是说要做小顶堆吧。应该是双stack,一个维护数据,另一个维护最小值。
    Pinnx
    Pinnx
    Nov 12, 2014
    15
    不是有个min函数么.
    xcv58
    xcv58
    Nov 12, 2014 via Smartisan T1
    16
    人家要 O(1) 你给弄个 O(n log n) Python 躺枪啊。
    rrfeng
    rrfeng
    Nov 12, 2014
    17
    维护『一个』最小值的话 pop 了咋办?
    zhchbin
    zhchbin
    Nov 12, 2014
    18
    ```python
    class MinStack:
    def __init__(self):
    self.data = []
    self.min_data = []

    def pop(self):
    if not self.data:
    return None

    self.min_data.pop()
    return self.data.pop()

    def push(self, x):
    self.data.append(x)
    if not self.min_data:
    self.min_data.append(x)
    else:
    self.min_data.append(min(self.min_data[-1], x))

    def top(self):
    return None if not self.data else self.data[-1]

    def getMin(self):
    return None if not self.data else self.min_data[-1]

    if __name__ == '__main__':
    min_stack = MinStack()
    data = [5, 2, 4, 3, -1, 0]
    for val in data:
    min_stack.push(val)
    print min_stack.getMin()

    min_stack.pop()
    print min_stack.getMin()
    min_stack.pop()
    print min_stack.getMin()
    ```

    经典的面试题目,刚学python,不知道写对了木有。
    zhchbin
    zhchbin
    Nov 12, 2014
    19
    囧。。还以为支持Mardown直接回复了。。自行缩进吧。
    frankzeng
    frankzeng
    Nov 12, 2014
    20
    return min(self.L)不就行了吗,干嘛自己实现?
    zhchbin
    zhchbin
    Nov 12, 2014
    21
    @frankzeng min(self.L) 的复杂度应该是O(n)。
    ryanking8215
    ryanking8215
    Nov 12, 2014
    22
    @zhchbin 好像不对吧,pop的时候,你怎么知道当前pop的那个值,在min_data里也需要pop掉,也即最大的那个?
    self.min_data.append(min(self.min_data[-1], x))
    这个明显不是O(1),怎么保证push是O(1)呢?
    scorpius
    scorpius
    Nov 12, 2014
    23
    @openroc 感觉这个正解
    happywowwow
    happywowwow
    Nov 12, 2014
    24
    o(1)的如何实现? 每次push的时候维护一个最小值?但请问pop的时候不是需要查询是否这个维护的值被pop了么?又需要重新找出最小的

    感觉得 双栈 或者 一栈一最小堆
    ipconfiger
    ipconfiger
    Nov 12, 2014
    25
    leetcode 里用Python写的话一个栈就Memory溢出了,2个还不爆浆?
    picy
    picy
    OP
    Nov 12, 2014 via iPhone
    26
    双栈的话会超出内存限制。无语了
    frankzeng
    frankzeng
    Nov 12, 2014
    27
    @openroc https://gist.github.com/openroc/196642a254a542e4e80f.js 这一个请求是不是你弄的?这一串东西把整个贴拉到奇慢无比,这算不算是v2ex的bug呢?
    openroc
    openroc
    Nov 12, 2014
    28
    gist被墙了。呵呵
    openroc
    openroc
    Nov 12, 2014
    29
    @frankzeng 请科学上网。:)
    takato
    takato
    Nov 12, 2014
    30
    @bcxx 感谢- -。笔误- -。。
    yakiang
    yakiang
    Nov 12, 2014
    31
    我能说这是上个月珍爱网校招数据岗位的一道笔试题吗
    ChanneW
    ChanneW
    Nov 12, 2014
    32
    我的第一想法是, 拖慢 pop push 速度,每次操作都更新最小值. 反而获取最小值只是把值返回.
    这样应该能过机器测试了,懒人的程序只做到刚好能用.
    caiych
    caiych
    Nov 12, 2014
    33
    跟python和list都没什么关系……
    LZ需要学习一下基本的数据结构…这东西叫堆或者优先队列什么的…
    ---
    Python自带的优先队列居然没有top或者front这样的方法…只能拿出来看……
    bcxx
    bcxx
    Nov 12, 2014
    34
    https://github.com/bcho/homework/blob/master/oj/leetcode/min_stack.py 的确是用两个 list 就可以过啊……


    @caiych 用优先队列也不是 O(1) 的…… 另外用 https://docs.python.org/2/library/heapq.html#heapq.nsmallest 这个就可以获取 top 和 front 了吧……
    zhchbin
    zhchbin
    Nov 12, 2014
    35
    @ipconfiger @janstk 双栈可以过啊。。在上面的版本做空间上的优化。

    @ryanking8215 其实估计是排版的问题导致你没看清楚代码逻辑,懒得解释哈。
    caiych
    caiych
    Nov 12, 2014
    37
    @bcxx
    重新读了一遍题,发现想当然了。。。
    takato
    takato
    Nov 12, 2014
    38
    @gt11799 堆的插入操作是O(logn)的
    takato
    takato
    Nov 12, 2014
    39
    双栈可以的原因是因为栈不能pop任意位置,而只能pop顶,所以只需要发现目前值小于等于当前最小值的时候,push一个最小值的栈则可,否则就不push。
    pop的时候先检验最小堆栈顶是不是这个元素,是则pop,否则不变
    ryanking8215
    ryanking8215
    Nov 12, 2014
    40
    @yakiang 这是leetcode上的题,主要是要求各操作都是O(1)的时间复杂度
    ryanking8215
    ryanking8215
    Nov 12, 2014
    41
    @zhchbin 确实看错了,:)
    dingyaguang117
    dingyaguang117
    Nov 12, 2014
    42
    pair的单栈,哈哈 就是比较浪费空间,有些最小值不必要存~
    push:
    -> push tuple(num, min)

    pop:
    -> pop tuple(num, min)
    picy
    picy
    OP
    Nov 12, 2014
    43
    好吧终于过了,感谢上面回复的各位。
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   1969 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 109ms · UTC 04:07 · PVG 12:07 · LAX 20:07 · JFK 23:07
    ♥ Do have faith in what you're doing.