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

算法题求思路

  •  
  •   letianqiu · 10 天前 · 1261 次点击
    给定一个大顶堆,元素已知。求能够生成这个大顶堆的元素插入顺序中,大的元素后插的顺序。
    堆是[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
        1
    kaliu   10 天前
    没看懂问题描述。
        2
    monkeymonkey   10 天前
    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。
    依次类推求出一个解,但是有可能只是其中一个解。
        3
    twistoy   10 天前
    @monkeymonkey #2 我觉得他说的 大的元素后插 应该指的是 输出的序列应该是字典序最小的那个
        4
    twistoy   10 天前   ♥ 1
    猜测题目的描述的意思是:给定一个大根堆,求一个数列可以生成这个大根堆;如果有多个解,需求那个字典序最小的。
    思路大概是:最后被 push 到堆的数,一定出现在从最后一个数到根的那条链上的,所以每次尝试在这条链上找一个深度最大的满足条件 A 的数,那么这个数就应该是当前考虑的最后一个被插入的数。
    条件 A:一个在我们考虑的这条链上的 X,所有深度比 X 大(也就是在 X 下面)的数都应该没有兄弟,或者大于等于其兄弟。
    我写了一个代码在
        5
    letianqiu   10 天前
    @twistoy 的确是你说的意思。但是你的条件 A 不是非常理解。比如[45,24,27,2,16],最后插入的元素是 24,觉得不满足你说的条件 A。24 的左孩子是 2,右孩子是 16。int nxt = cur ^ 1;这个异或也不是很理解。
        6
    twistoy   10 天前 via Android
    @letianqiu 堆 45 24 27 2 16, 最后一个数到根的链是 45, 24, 16。16 是一定可以作为最后一个的, 24 可以作为最后一个是因为 16 比他的兄弟 2 大, 45 不能是最后一个因为 24 比他的兄弟 27 小。那个异或的意思是哪个编号的兄弟节点的编号。
        7
    letianqiu   10 天前
    @twistoy 明白了。思路和 @monkeymonkey 说的一样。非常感谢。
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   2576 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.0 · 40ms · UTC 06:15 · PVG 14:15 · LAX 23:15 · JFK 02:15
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1