FB Intern 一面

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

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

朋友你跟我电面的问题一样 但我面全职 加油

magichqg 发表于 2017-2-15 06:29
N固定，K很大的时候，maintain 一个 N-k+1大小的max heap，这样heap pop出来的就是第k小的，不需要再trav ...

应该是min heap吧。。。。

请教一下楼主，如果是仅仅找第K个近的点，那直接quickselect用O(n)的时间就可以找到了把。
如果是找前K个近的所有点的话，如果不要求排序，先quickselect用O(n)的时间找到第k个近的点，然后在traverse所有点，凡是比这个点更近的才保留，这样也是O(n)就够了。
如果所有点要排序的话，那只能用max_heap了，就是O(nlog(k))了。