Amazon SDE Intern 热腾腾面经（估计跪了）

这题是利口 二九五

利口尔久舞？今天看地里有人也说这道题了，手撕hard太可怕了

ljhgod 发表于 2019/10/29 10:28:36
居然说不行？？？这不是故意坑你么！！即便和面试官争论一般不会也有好事吧.

虽然被坑了，但还是应该argue的

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

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

感觉两个heap可以做？把需要删除的数字存在maxheap的最下面就行了，对结果不会有影响，只要另外分情况讨论下当前元素个数>k还是<=k就行了。

您好！
本帖隐藏的内容需要积分高于 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

为什么不用list呢，collections.sort（）排一下，最后取最大K个数的中位数？求问

doubly linked list, 只maintain k个最大的，然后median指针在中间index k/2那一个。每一次插入一个比k中最小值大的时候，把最小那个从尾巴给pop out掉。每次都是o(k)。不过总体的话是O(KN)。

wwanxh 发表于 2019/12/09 14:23:13
doubly linked list, 只maintain k个最大的，然后median指针在中间index k/2那一...

用Binary Search的话就可以O(logk)了