Bloomberg二次电面

老印 挺nice的一直提示，但是没刷过类似的 平时用heap也直接调library 这回惨烈了后来发现lintcode上面有

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

siftdown的方法是O(n)的：

非要o(n)么?

readman 发表于 2016-7-8 01:05
非要o(n)么?

O(nlgn)的话调数组的sort就可以了。。。所以估计人家想要O(n)

Fustang 发表于 2016-7-8 02:26
O(nlgn)的话调数组的sort就可以了。。。所以估计人家想要O(n)

uhm...heap 到 bst....我觉得n能建树么....我一时没法确定...

readman 发表于 2016-7-8 02:43
uhm...heap 到 bst....我觉得n能建树么....我一时没法确定...

看我原帖 最后给了heapify的O(n) link...

这个还是很有意思的，至于为什么build heap是O(n)可以看这个:

http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf

Fustang 发表于 2016-7-8 02:47
看我原帖 最后给了heapify的O(n) link...

我说的是heap->bst 不是build heap

readman 发表于 2016-7-8 03:26
我说的是heap->bst 不是build heap

不是bst吧，只是binary tree