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

算法题求解,关于排序

  •  
  •   hwdef · 21 天前 · 546 次点击

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

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

    15 回复  |  直到 2018-07-01 07:14:42 +08:00
        1
    linap   21 天前 via Android   ♥ 1
    一个 10 大小的数组。遍历数据,数据如果大于数组中的最小的数,替换那个数
        2
    twistoy   21 天前 via Android   ♥ 1
    维护一个大小为 10 的大根堆。时间复杂度 O(n)
        3
    aaax7676   21 天前 via Android   ♥ 2
    top k 问题,维护个容量为 k 的堆
        4
    sylxjtu   21 天前 via Android   ♥ 1
    跑 10 遍 nth_element?
        5
    neosfung   21 天前 via iPhone   ♥ 1
    @twistoy 小根堆
        6
    Win78   21 天前 via Android   ♥ 1
    优先队列
        7
    easylee   21 天前 via Android   ♥ 1
    题目我没有什么好的解决办法,但是搁在实际应用中,我是后台定时排序,然后存储标记,这样一来虽然不能做到实时查询,但是很方便,不会牺牲时间复杂度。
        8
    twistoy   20 天前 via Android   ♥ 1
    @neosfung 取最大的 10 个应该是大根堆吧
        9
    neosfung   20 天前   ♥ 1
    @twistoy 小根堆,堆顶是前十个最大数中,最小的数。新进来的数和堆顶比较大小,比堆顶大的,就把堆顶换成新进来的数,然后调整堆;否则比堆顶小的,就不管了。
        10
    hwdef   20 天前
    @linap 这个方法确实很简单
        11
    chashao   20 天前 via Android
    @twistoy 我觉得时间复杂度是 O(10lgn)
        12
    twistoy   19 天前
    @chashao 怎么可能…
    n 个数至少要遍历一遍,至少是 O(n)
        13
    chashao   19 天前 via Android
    @twistoy 每次建堆不是 O(lgn)么……
        14
    twistoy   19 天前
    @chashao 但是堆大小是固定 10 的
        15
    Templ1   18 天前 via Android
    静态查询-->右转各种堆,各种排序
    动态查询-->平衡树
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   实用小工具   ·   674 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 18ms · UTC 19:28 · PVG 03:28 · LAX 12:28 · JFK 15:28
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1