V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hwdef
V2EX  ›  算法

算法题求解,关于排序

  •  
  •   hwdef · 2018-06-28 22:41:27 +08:00 · 3500 次点击
    这是一个创建于 2351 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在百万级数据中怎么找到最大的 10 个数?

    我觉得应该不会用排序,只会用标记,这么大的数据,什么排序也都太慢了。 可能是我想的太简单 不知道大家有什么想法。

    15 条回复    2018-07-01 07:14:42 +08:00
    linap
        1
    linap  
       2018-06-28 22:55:05 +08:00 via Android   ❤️ 1
    一个 10 大小的数组。遍历数据,数据如果大于数组中的最小的数,替换那个数
    twistoy
        2
    twistoy  
       2018-06-28 22:55:44 +08:00 via Android   ❤️ 1
    维护一个大小为 10 的大根堆。时间复杂度 O(n)
    aaax7676
        3
    aaax7676  
       2018-06-28 22:57:15 +08:00 via Android   ❤️ 2
    top k 问题,维护个容量为 k 的堆
    sylxjtu
        4
    sylxjtu  
       2018-06-28 23:30:25 +08:00 via Android   ❤️ 1
    跑 10 遍 nth_element?
    neosfung
        5
    neosfung  
       2018-06-28 23:34:40 +08:00 via iPhone   ❤️ 1
    @twistoy 小根堆
    Win78
        6
    Win78  
       2018-06-29 00:53:50 +08:00 via Android   ❤️ 1
    优先队列
    easylee
        7
    easylee  
       2018-06-29 01:03:05 +08:00 via Android   ❤️ 1
    题目我没有什么好的解决办法,但是搁在实际应用中,我是后台定时排序,然后存储标记,这样一来虽然不能做到实时查询,但是很方便,不会牺牲时间复杂度。
    twistoy
        8
    twistoy  
       2018-06-29 10:36:43 +08:00 via Android   ❤️ 1
    @neosfung 取最大的 10 个应该是大根堆吧
    neosfung
        9
    neosfung  
       2018-06-29 10:49:43 +08:00   ❤️ 1
    @twistoy 小根堆,堆顶是前十个最大数中,最小的数。新进来的数和堆顶比较大小,比堆顶大的,就把堆顶换成新进来的数,然后调整堆;否则比堆顶小的,就不管了。
    hwdef
        10
    hwdef  
    OP
       2018-06-29 11:46:01 +08:00
    @linap 这个方法确实很简单
    chashao
        11
    chashao  
       2018-06-29 15:37:52 +08:00 via Android
    @twistoy 我觉得时间复杂度是 O(10lgn)
    twistoy
        12
    twistoy  
       2018-06-30 19:25:15 +08:00
    @chashao 怎么可能…
    n 个数至少要遍历一遍,至少是 O(n)
    chashao
        13
    chashao  
       2018-06-30 20:03:05 +08:00 via Android
    @twistoy 每次建堆不是 O(lgn)么……
    twistoy
        14
    twistoy  
       2018-06-30 21:43:17 +08:00
    @chashao 但是堆大小是固定 10 的
    Templ1
        15
    Templ1  
       2018-07-01 07:14:42 +08:00 via Android
    静态查询-->右转各种堆,各种排序
    动态查询-->平衡树
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3568 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 04:37 · PVG 12:37 · LAX 20:37 · JFK 23:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.