V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tesorouo
V2EX  ›  问与答

找最大的第 m 个数问题

  •  1
     
  •   tesorouo · 2020-06-07 17:19:06 +08:00 · 2567 次点击
    这是一个创建于 1628 天前的主题,其中的信息可能已经有所发展或是发生改变。
    原始数组只能从第一个开始访问一次,如何最快的在空间 O(m)的复杂度下找到第 m 个最大的数?
    22 条回复    2020-06-07 21:50:23 +08:00
    msg7086
        1
    msg7086  
       2020-06-07 17:26:07 +08:00   ❤️ 1
    小顶堆?
    arjen
        2
    arjen  
       2020-06-07 17:27:39 +08:00 via Android   ❤️ 1
    楼上正解,大小为 m 的小顶堆
    tesorouo
        3
    tesorouo  
    OP
       2020-06-07 17:29:27 +08:00
    @arjen
    @msg7086

    小顶堆好像没办法做到时间 O(n) (即不为最快),答案说时间可以做到 O(n),想破脑袋想不出。。
    arjen
        4
    arjen  
       2020-06-07 17:34:52 +08:00 via Android
    @tesorouo 一次遍历就可以吧?每个元素与堆顶比较 ,比堆顶元素大即入堆,小则抛弃,最后堆顶元素为 top k 大元素。
    gzfrankie
        5
    gzfrankie  
       2020-06-07 17:41:05 +08:00 via iPhone   ❤️ 2
    小顶堆解法时间复杂度是 O(n+nlogm),当 n 远大于 m 时,其实就是 O(n).据我所知没有更优解法。
    4rnold
        6
    4rnold  
       2020-06-07 17:44:45 +08:00   ❤️ 1
    [ [算法] Quick Select - LinMiaoj - 博客园]( https://www.cnblogs.com/LinMiaoJia/p/QuickSelect.html)
    gwy15
        7
    gwy15  
       2020-06-07 17:52:01 +08:00
    @4rnold 他要求一次遍历且不可修改。
    tesorouo
        8
    tesorouo  
    OP
       2020-06-07 17:53:25 +08:00
    @4rnold 我不知道我理解的对不对,但是这个如果是最初数组每个元素只能访问一次的情况下应该空间复杂度不止 O(m)
    gwy15
        9
    gwy15  
       2020-06-07 18:08:06 +08:00 via Android   ❤️ 1
    @tesorouo 这个可以原地 o1 空间,on 时间。就是快排只排一半。但是你要求单次遍历(只给一个单向迭代器),这个不适用
    msg7086
        10
    msg7086  
       2020-06-07 18:33:39 +08:00
    @tesorouo #3
    每一次替换操作的时间复杂度是 logm,这里 m 相当于是题目给定的数字,算是常量,所以 logm 也是常量。
    n+nlogm 的复杂度就等于是 O(n)了。
    vindurriel
        11
    vindurriel  
       2020-06-07 19:33:57 +08:00 via iPhone   ❤️ 1
    @tesorouo 楼主您题里说的是空间复杂度 O(m) 明显是堆 并没说时间复杂度 事实上实际场景里数组可以是无限长的 stream 在有限的内存里处理 此处空间复杂度比时间复杂度更有意义
    tesorouo
        12
    tesorouo  
    OP
       2020-06-07 19:36:58 +08:00
    @vindurriel 对的我也是这样认为的,但是就是 O(n)的时间完全说不通,是一个比较偏向于理论的问题
    rrfeng
        13
    rrfeng  
       2020-06-07 19:43:00 +08:00 via Android   ❤️ 1
    不用堆也可以啊,一个长 m 的数组,遍历到的数字往里做插入排序,遍历完最小的那个不就是么。
    m 大的时候时间复杂度会比较高而已…

    降低插入排序的办法可以用链表

    当然堆可能是最好的
    rabbbit
        14
    rabbbit  
       2020-06-07 19:45:05 +08:00   ❤️ 1
    双调排序可以做到 O(logn),但不符合只遍历一次.找出 k 个最大的数一般都是用堆排序.
    tesorouo
        15
    tesorouo  
    OP
       2020-06-07 19:50:13 +08:00
    @rrfeng 这个应该是不对的,做插入的时候每次比较都是 O(m),就算不看 m 的排序都有(n-m)个元素要进行这个操作,应该是差于堆的
    tesorouo
        16
    tesorouo  
    OP
       2020-06-07 19:52:25 +08:00
    @rabbbit 这个空间复杂度应该是超了很多了
    rabbbit
        17
    rabbbit  
       2020-06-07 19:54:25 +08:00
    @tesorouo
    这个是并行排序算法,空间肯定是超的.
    samlua
        18
    samlua  
       2020-06-07 20:07:17 +08:00 via iPhone
    quick sort 的 partition ?每次放弃另一边 平均复杂度 O(n)
    samlua
        19
    samlua  
       2020-06-07 20:08:59 +08:00 via iPhone
    @samlua 失误 没有看清楚题目限制
    rrfeng
        20
    rrfeng  
       2020-06-07 20:59:28 +08:00 via Android
    @tesorouo
    又没要求时间复杂度啊,而且我也说了会很高。如果不了解堆这是容易想到的一个思路。
    opengps
        21
    opengps  
       2020-06-07 21:05:45 +08:00
    woc,你们怎么又什么都懂
    hello2060
        22
    hello2060  
       2020-06-07 21:50:23 +08:00 via iPhone
    @opengps leetcode 里面很常见的类型啦
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1008 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 20:05 · PVG 04:05 · LAX 12:05 · JFK 15:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.