亚马逊intern面经

wait4it 发表于 2015-12-31 07:13
我觉得用list的花，quick select你不知道list的位置，不能跟vector一样直接调用index，我感觉是这样

这样的话这个问题就没法用quick select 做到O(n)了吧？  你的那个O(nlogK)的方法我没有很懂  如果把所有都放进maxheap的话取K次那就是O(klogn)   但是用你的方法K个值是怎么取的呢？

iPhD 发表于 2015-12-28 11:32
PQ用的是Binary Heap实现的。。。你可以上网看些教程或公开课了解下。。。

heap也是遍历所有的数才知道哪个大小的。

zealot5209 发表于 2016-1-3 15:04
这样的话这个问题就没法用quick select 做到O(n)了吧？  你的那个O(nlogK)的方法我没有很懂  如果把所有 ...

保留一个有K个元素的heap就好了，每次加一个元素再弹一个元素

wcyz666 发表于 2016-1-3 17:03
保留一个有K个元素的heap就好了，每次加一个元素再弹一个元素

弹出来的元素是这K个里面最大的  但如果这K个元素里没有一个是n个元素前K大的元素呢？

wcyz666 发表于 2016-1-3 17:03
保留一个有K个元素的heap就好了，每次加一个元素再弹一个元素

比如 1,2,3,4,5  K=2    1，2放进heap 弹出来 2， 但这个2没有用啊

zealot5209 发表于 2016-1-3 17:55
比如 1,2,3,4,5  K=2    1，2放进heap 弹出来 2， 但这个2没有用啊

比如 1,2,3,4,5  K=2

1 放进去 (队元素1)
2 放进去 (队元素1 2)
3 放进去，queue.size() > K. 弹出1  (队元素2 3)
4 放进去，queue.size() > K. 弹出2  (队元素3 4)
5 放进去，queue.size() > K. 弹出3  (队元素4 5)

最后弹出队首元素，这就是答案

wcyz666 发表于 2016-1-3 19:40
比如 1,2,3,4,5  K=2

1 放进去 (队元素1)

原来如此 受教了

xiaozhuxiaozhu 发表于 2016-1-3 15:07
heap也是遍历所有的数才知道哪个大小的。

同学，你真的要去复习heap的知识。wait4it说的没错。

zealot5209 发表于 2016-1-3 17:54
弹出来的元素是这K个里面最大的  但如果这K个元素里没有一个是n个元素前K大的元素呢？

这个heap是个min heap， 弹出来是里面最小的。

wait4it 发表于 2015-12-29 13:57
好像是可以，但是我当时没有想到，他也没问我更快的方法。所以我就这么做了，就是最后一个follow up给的 ...

想问下楼主follow up，给的是list的iterator怎么弄啊，个人感觉还是可以用min heap做啊