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

算法题求解,关于排序

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

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

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

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