11/10 脸书全职挂经 非leetcode题！！！！！！！！！！

woshilindan 发表于 2017-11-11 16:37
对在哪里 不是跟priorityqueue做法一样的吗 都要先遍历原数组一遍 如果原数组1有1 million个不是很浪费时 ...

我问你如果k非常大，你的pq空间复杂度是多少。你的时间复杂度也是nlogk。k很大就几乎nlogn了。用array空间是常数，时间复杂度是o(n)。

zachzuogwu 发表于 2017-11-12 01:41
楼主的例子 [9,9,5,3,3,7,1] k =3, top 3 = 9+9+7。请问下，找top k个和找top k个出来再相加，有区别吗？

leetcode内道题是top kth element 只return一个

补充内容 (2017-11-12 02:50):
nvm我理解错你的意思了

cutehuazai 发表于 2017-11-12 02:41
我问你如果k非常大，你的pq空间复杂度是多少。你的时间复杂度也是nlogk。k很大就几乎nlogn了。用array空 ...

而且我不理解楼主为啥要纠结在数组都要扫一遍，o(n)和o(nlogk)还是有差的呀。尤其当k很大的时候,pq即占空间且更慢

woshilindan 发表于 2017-11-11 16:38
当时面试时查到了但是早忘了怎么搞的

你array的做法本来就已经是在做bucket sort了。

woshilindan 发表于 2017-11-11 16:55
bucket sort解法和array解法都差不多都是O(n)?

恩恩恩恩 是的

楼主 这道题就是leetcode原题
https://discuss.leetcode.com/topic/14597/solution-explained?page=1
借用partition的思想 running time O(n)
原题return nums[k]
你return sum(nums[k:])就吼了啊
pat pat

多谢分享

iwantanintern 发表于 2017-11-12 02:49
leetcode内道题是top kth element 只return一个

补充内容 (2017-11-12 02:50):

top k frequent element 好像是伞思旗 解法是相通的

用pq插入加查询还不如你直接sort。。。小哥提醒的bucket仁至义尽了。。。

lz你的问题主要在于你不知道priority queue的插入和pop都是logk的。而counting插入是O（1）的。所以一个是nlogk一个是n，当然不一样。