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

HNAKXR 发表于 2017-11-11 14:17
0-9之间这么小的范围算是挺明显的bucket或者radix sort暗示了吧，算法课只要讲到基本都会这么考，当然count ...

当时面试时查到了但是早忘了怎么搞的

woshilindan 发表于 2017-11-11 16:36
priorityqueue和array不都是一样的复杂度？到要先扫一遍？？？

空间吧，pq空间n，array只有10个~

AlanWu 发表于 2017-11-11 16:46
空间吧，pq空间n，array只有10个~

嗷嗷嗷....

woshilindan 发表于 2017-11-11 16:48
嗷嗷嗷....

标准pq做法是维护size k的，那样空间只有k

硅谷吴彦祖 发表于 2017-11-11 13:40
如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn

如果用bucket sort n个元素 ...

bucket sort解法和array[index]解法都差不多都是O(n)?

AlanWu 发表于 2017-11-11 16:55
标准pq做法是维护size k的，那样空间只有k

对对对.......

你面试的小哥是不是名字开头是r啥啥 看起来像印度人名字？

利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)

zachzuogwu 发表于 2017-11-12 01:26
利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)

这明明跟leetcode 题不一样

iwantanintern 发表于 2017-11-12 01:32
这明明跟leetcode 题不一样

楼主的例子 [9,9,5,3,3,7,1] k =3, top 3 = 9+9+7。请问下，找top k个和找top k个出来再相加，有区别吗？