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

算法题求思路

  •  
  •   letianqiu · 2017-10-12 21:36:05 +08:00 · 3163 次点击
    这是一个创建于 2359 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定一个大顶堆,元素已知。求能够生成这个大顶堆的元素插入顺序中,大的元素后插的顺序。
    堆是[27,12,18],插入顺序是 12,18,27
    堆是[45,24,27,2,16], 插入顺序是 2 , 27 , 45 , 16 , 24
    目前只能想到 naive 的 n!的暴力求解,但是肯定不符合要求。求高效算法
    7 条回复    2017-10-13 08:56:42 +08:00
    kaliu
        1
    kaliu  
       2017-10-12 22:21:43 +08:00
    没看懂问题描述。
    monkeymonkey
        2
    monkeymonkey  
       2017-10-12 23:17:30 +08:00   ❤️ 1
    LZ 的题目确实描述不清楚。
    猜测是有一个空的大顶堆,按顺序插入一系列数字,最后形成一个堆(题目给出),求能够生成题目所给堆的数字插入顺序。
    比如[27,12,18],
    1. 先有空堆[]
    2. 插入 12, 变成[12]
    3. 插入 18,sift up 18,变成[18,12]
    4. 插入 27,sift up 27,变成[27,12,18]
    所以 12,18,27 是一个解
    但是 18,12,27 也是一个解。
    由此可知,解可能不唯一。

    提供一个思路:
    比如[45,24,27,2,16]
    既然是最大堆,那我们从最顶上,也就是最大的数 45 开始,假设 45 是最后一个插入的数。
    由 siftup 的性质可知,最后一个数从下往上走过的路径只能是 16->24->45.
    把 45 与 24 交换,发现 24 比 27 小,大顶堆不成立,所以不是 45。

    然后测试这条路上的 24,与 16 交换,并且从堆中移除,发现得到的新堆[45,16,27,2]是一个合格的大顶堆。
    所以最后一个数是 24。

    同理得到倒数第二个数是 16。
    依次类推求出一个解,但是有可能只是其中一个解。
    twistoy
        3
    twistoy  
       2017-10-12 23:45:32 +08:00
    @monkeymonkey #2 我觉得他说的 大的元素后插 应该指的是 输出的序列应该是字典序最小的那个
    twistoy
        4
    twistoy  
       2017-10-13 01:21:51 +08:00   ❤️ 1
    猜测题目的描述的意思是:给定一个大根堆,求一个数列可以生成这个大根堆;如果有多个解,需求那个字典序最小的。
    思路大概是:最后被 push 到堆的数,一定出现在从最后一个数到根的那条链上的,所以每次尝试在这条链上找一个深度最大的满足条件 A 的数,那么这个数就应该是当前考虑的最后一个被插入的数。
    条件 A:一个在我们考虑的这条链上的 X,所有深度比 X 大(也就是在 X 下面)的数都应该没有兄弟,或者大于等于其兄弟。
    我写了一个代码在 https://gist.github.com/TwIStOy/a0b0cb1317ed9bf4d9a805222edfc3e8
    letianqiu
        5
    letianqiu  
    OP
       2017-10-13 07:21:06 +08:00
    @twistoy 的确是你说的意思。但是你的条件 A 不是非常理解。比如[45,24,27,2,16],最后插入的元素是 24,觉得不满足你说的条件 A。24 的左孩子是 2,右孩子是 16。int nxt = cur ^ 1;这个异或也不是很理解。
    twistoy
        6
    twistoy  
       2017-10-13 08:35:19 +08:00 via Android
    @letianqiu 堆 45 24 27 2 16, 最后一个数到根的链是 45, 24, 16。16 是一定可以作为最后一个的, 24 可以作为最后一个是因为 16 比他的兄弟 2 大, 45 不能是最后一个因为 24 比他的兄弟 27 小。那个异或的意思是哪个编号的兄弟节点的编号。
    letianqiu
        7
    letianqiu  
    OP
       2017-10-13 08:56:42 +08:00
    @twistoy 明白了。思路和 @monkeymonkey 说的一样。非常感谢。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3974 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 05:13 · PVG 13:13 · LAX 22:13 · JFK 01:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.