肥死不可一面挂经

10.15 面的，华人小哥，人很好题不难

题目如下

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

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

两道题时间复杂度都没答好，20号收到拒信。

还是很后悔的，很幸运收到fb电面却没有准备充分就去面，总是一手好牌被自己打烂，如果能再推迟两周把高频多刷几遍可能不会这样。



补充内容 (2018-10-26 04:15):
求米谢谢！

xingzhelew 发表于 2018-10-26 04:46
若问一下第一题用优先队列复杂度不是nlogn？

nlogk呀，直接排序就是nlogn所以说很蠢

T大农民伯伯 发表于 2018-10-30 07:38
nlog k的做法是建立大小为ｋ的堆，把ｎ个元素往里面塞同时往外面排。ｋlogn　是先建立大小为ｎ的堆，往外 ...

建堆是O(N)，K次调整是O(KlgN)，总共O(N+KlgN)

木木木一 发表于 2018-10-28 11:30
请问有klogn 和 nlogk两种情况吗？能简单说明下吗？为什么klogn用的空间更多呢？谢谢！

nlog k的做法是建立大小为ｋ的堆，把ｎ个元素往里面塞同时往外面排。ｋlogn　是先建立大小为ｎ的堆，往外面排ｋ个元素。

若问一下第一题用优先队列复杂度不是nlogn？

第一题用算一遍距离用后，用selection algorithm,O(N)复杂度这样做可以吗？

glenjoker 发表于 2018-10-26 05:56
第一题用算一遍距离用后，用selection algorithm,O(N)复杂度这样做可以吗？

randomized quickselect吗？

asdadd 发表于 2018-10-26 08:06
randomized quickselect吗？

deterministic selection

这里的点是Point类嘛，还是用数组表示

论坛匿名用户 发表于 2018-10-26 04:47
nlogk呀，直接排序就是nlogn所以说很蠢

噢噢，是的

tianqingche 发表于 2018-10-26 14:13
这里的点是Point类嘛，还是用数组表示

point，但无所谓没有让实现

其实你说klogn也是可以的。先建堆，再吐k个元素