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

20180325 今日算法

  •  
  •   gbin · 2018-03-25 13:57:33 +08:00 via Android · 3181 次点击
    这是一个创建于 2435 天前的主题,其中的信息可能已经有所发展或是发生改变。
    输出数组 s 前 k 个大的元素( k 不大于数组的长度)

    如:
    s =[4,2,8,3,6,5],k=3
    则输出
    6,5,8(输出顺序不必考虑)
    13 条回复    2018-03-25 19:14:56 +08:00
    lhx2008
        1
    lhx2008  
       2018-03-25 14:06:00 +08:00 via Android   ❤️ 1
    维护一个 k 大小的最小堆
    gbin
        2
    gbin  
    OP
       2018-03-25 14:09:54 +08:00 via Android
    @lhx2008 正解。想起有一次面试问我这个题,我说了思路,那时候最小堆还真写不出来。
    clearbug
        3
    clearbug  
       2018-03-25 14:16:49 +08:00 via Android
    利用快排的思维
    Andiry
        4
    Andiry  
       2018-03-25 14:19:14 +08:00
    QuickSort partition
    wjm2038
        5
    wjm2038  
       2018-03-25 14:57:57 +08:00 via Android
    @gbin 请问下最小堆是啥啊
    aidaizyy
        6
    aidaizyy  
       2018-03-25 15:10:01 +08:00
    不考虑顺序的话,没必要用最小堆,用快排思想就可以了,时间复杂度要低一些。
    zjp
        7
    zjp  
       2018-03-25 15:18:08 +08:00 via Android
    正在做 LeetCode 215.Kth Largest Element in An array
    才发现上学期刚学过快速选择…
    gbin
        8
    gbin  
    OP
       2018-03-25 15:57:55 +08:00 via Android
    @wjm2038 最小堆就是一种有序的完全二叉树,父结点总是不小于子结点。你可以看一下 wikipedia https://zh.wikipedia.org/zh-hans/%E6%9C%80%E5%A4%A7%E2%80%94%E6%9C%80%E5%B0%8F%E5%A0%86
    mrcn
        9
    mrcn  
       2018-03-25 17:44:50 +08:00 via Android
    堆应该是 O(kLog n),快排思想应该也是这个?
    GGGG430
        10
    GGGG430  
       2018-03-25 17:47:19 +08:00 via iPhone
    快排倒叙取 topk/小顶堆 /维护一个大小为 k 的数组
    stevenbipt
        11
    stevenbipt  
       2018-03-25 17:53:17 +08:00 via Android
    top k 问题⊙▽⊙才在算法导论上学了这个算法,当初自己没学这个的时候就直接排序然后找到最大的数字输出然后删除最大的数字,然后继续找出来最大输出然后删除,这样进行 k 次
    stevenbipt
        12
    stevenbipt  
       2018-03-25 17:56:18 +08:00 via Android
    这个问题不要求排序直接用快速排序的思想效率应该是相对比较高的
    victor97
        13
    victor97  
       2018-03-25 19:14:56 +08:00 via Android
    快排的思路,时间复杂度是 O(n)的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2444 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 02:25 · PVG 10:25 · LAX 18:25 · JFK 21:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.