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

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

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

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

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，当然不一样。