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

千万条记录的数组找 Top100,什么算法时间复杂度较低

  •  
  •   wangfyyy · 2020-06-15 14:31:50 +08:00 · 1751 次点击
    这是一个创建于 1382 天前的主题,其中的信息可能已经有所发展或是发生改变。

    时间复杂度最好小于 O(nlogn)

    8 条回复    2020-07-04 06:10:34 +08:00
    Kilerd
        1
    Kilerd  
       2020-06-15 14:35:14 +08:00
    限制 nLogN 那就快排一下,取前 100 (反正你也没要求空间复杂度
    xupefei
        2
    xupefei  
       2020-06-15 14:36:41 +08:00 via iPhone
    heap sort,复杂度 n log100
    Perry
        3
    Perry  
       2020-06-15 14:41:51 +08:00 via iPhone
    先找到没有排好的 top 100
    B1ankCat
        4
    B1ankCat  
       2020-06-15 17:02:48 +08:00
    按理论来说最小堆就行
    takemeaway
        5
    takemeaway  
       2020-06-15 17:12:18 +08:00
    O(1)即可
    unixeno
        6
    unixeno  
       2020-06-15 17:18:22 +08:00 via Android
    构建一个 100 元素的小顶堆
    然后遍历数组,大于堆顶元素的时候就交换,然后调整堆
    wangfyyy
        7
    wangfyyy  
    OP
       2020-06-15 18:22:37 +08:00
    看来这不是一道经典的面试题
    yishanhe
        8
    yishanhe  
       2020-07-04 06:10:34 +08:00
    其实用堆的话 ,空间复杂度 是 O(k) 时间复杂度是 O(nlogk)
    这里的 k 就是 100
    已经比 O(nlogn) 小了

    如果要找比 O(nlogk) 还少的,那么就只能空间换时间了,可以用 bucket sort
    时间复杂度 O(n) 空间复杂度 也是 O(n)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1181 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:06 · PVG 07:06 · LAX 16:06 · JFK 19:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.