刚面玩linkedIn求人品

billupus · 2014-10-29 06:02:28

那是的。如果你pop是唯一最大值，那max要更新

dragonmigo · 2014-11-14 07:06:30

lunaughty 发表于 2014-10-16 04:11
这个感觉可以用一个链表和一个堆，链表当作栈使用，插入删除的时候同时操作那个堆就行了。

正解，这样所有操作都是 O(1).

yvetterowe · 2014-11-17 14:26:11

billupus 发表于 2014-10-18 04:14
好主意，但是其实和两个堆复杂是一样的(只是少了一个堆变成1/2)

求问能不能具体解释一下链表+堆 /两个堆的解法？
堆的value存的是链表的node吗？以及链表是不是要用双链表...? thx!!

走路草May

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

kelmt

请问第一题可以用两条linked list求交点的方法找到第一个交汇点，就是最低共有父节点吗？

aplusplus

第二题doubly linked list + bst

averillzheng

billupus 发表于 2014-10-15 05:01
对就是每个node除了left和right还有个parent

Class Node {

感谢提供思路！！！

bobzhang2004

楼主第一题的意思是先两个node走到root计算出高度，然后再调到同一高度？

averillzheng

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

f1371342385

dragonmigo 发表于 2014-11-14 07:06
正解，这样所有操作都是 O(1).

这不是O1，这都是logn，pop，popMax，都是logn