fb实习电面面经

find the k-th largest number in an uns

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

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

=1000000000， k=10

yydcool 发表于 2016-11-8 06:37
用heap维护前k个

觉得应该用heap维护所有的n个，然后poll k次，这样时间复杂度是klogn

xiaozhuxiaozhu 发表于 2016-11-8 06:07
follow up怎么答的呢。
谢谢

用heap维护前k个

follow up用个k size 的min heap ？

follow up怎么答的呢。
谢谢

怕风 发表于 2016-12-4 02:15
维护所有的n个至少要nlogn吧

n个元素插入heap的复杂度是O(n)(这个我们算法课讲过)，每次pop出来的复杂度是O(logn)

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

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

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

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