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

20180325 今日算法

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

    如:
    s =[4,2,8,3,6,5],k=3
    则输出
    6,5,8(输出顺序不必考虑)
    13 回复  |  直到 2018-03-25 19:14:56 +08:00
        1
    lhx2008   2018-03-25 14:06:00 +08:00 via Android   ♥ 1
    维护一个 k 大小的最小堆
        2
    gbin   2018-03-25 14:09:54 +08:00 via Android
    @lhx2008 正解。想起有一次面试问我这个题,我说了思路,那时候最小堆还真写不出来。
        3
    clearbug   2018-03-25 14:16:49 +08:00 via Android
    利用快排的思维
        4
    Andiry   2018-03-25 14:19:14 +08:00
    QuickSort partition
        5
    wjm2038   2018-03-25 14:57:57 +08:00 via Android
    @gbin 请问下最小堆是啥啊
        6
    aidaizyy   2018-03-25 15:10:01 +08:00
    不考虑顺序的话,没必要用最小堆,用快排思想就可以了,时间复杂度要低一些。
        7
    zjp   2018-03-25 15:18:08 +08:00 via Android
    正在做 LeetCode 215.Kth Largest Element in An array
    才发现上学期刚学过快速选择…
        8
    gbin   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
        9
    mrcn   2018-03-25 17:44:50 +08:00 via Android
    堆应该是 O(kLog n),快排思想应该也是这个?
        10
    GGGG430   2018-03-25 17:47:19 +08:00 via iPhone
    快排倒叙取 topk/小顶堆 /维护一个大小为 k 的数组
        11
    stevenbipt   2018-03-25 17:53:17 +08:00 via Android
    top k 问题⊙▽⊙才在算法导论上学了这个算法,当初自己没学这个的时候就直接排序然后找到最大的数字输出然后删除最大的数字,然后继续找出来最大输出然后删除,这样进行 k 次
        12
    stevenbipt   2018-03-25 17:56:18 +08:00 via Android
    这个问题不要求排序直接用快速排序的思想效率应该是相对比较高的
        13
    victor97   2018-03-25 19:14:56 +08:00 via Android
    快排的思路,时间复杂度是 O(n)的
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3397 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 10:21 · PVG 18:21 · LAX 02:21 · JFK 05:21
    ♥ Do have faith in what you're doing.