楼主: inspration
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
cutehuazai 2017-11-12 02:41:01 | 只看该作者
全局:
woshilindan 发表于 2017-11-11 16:37
对在哪里 不是跟priorityqueue做法一样的吗 都要先遍历原数组一遍 如果原数组1有1 million个不是很浪费时 ...

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

使用道具 举报

🔗
iwantanintern 2017-11-12 02:49:43 | 只看该作者
全局:
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:51:18 | 只看该作者
全局:
cutehuazai 发表于 2017-11-12 02:41
我问你如果k非常大,你的pq空间复杂度是多少。你的时间复杂度也是nlogk。k很大就几乎nlogn了。用array空 ...

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

使用道具 举报

🔗
cutehuazai 2017-11-12 02:53:07 | 只看该作者
全局:
woshilindan 发表于 2017-11-11 16:38
当时面试时查到了但是早忘了怎么搞的

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

使用道具 举报

🔗
abcd1997 2017-11-12 03:22:57 | 只看该作者
全局:
woshilindan 发表于 2017-11-11 16:55
bucket sort解法和array解法都差不多都是O(n)?

恩恩恩恩 是的
回复

使用道具 举报

🔗
iwantanintern 2017-11-12 03:30:06 | 只看该作者
全局:
楼主 这道题就是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
回复

使用道具 举报

🔗
kungfu 2017-11-12 03:37:48 | 只看该作者
本楼:
全局:
多谢分享
回复

使用道具 举报

🔗
zachzuogwu 2017-11-12 03:55:25 | 只看该作者
全局:
iwantanintern 发表于 2017-11-12 02:49
leetcode内道题是top kth element 只return一个

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

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

使用道具 举报

🔗
gyzjay 2017-11-12 04:06:06 | 只看该作者
全局:
用pq插入加查询还不如你直接sort。。。小哥提醒的bucket仁至义尽了。。。
回复

使用道具 举报

🔗
rhbupt 2017-11-12 04:11:19 | 只看该作者
全局:
lz你的问题主要在于你不知道priority queue的插入和pop都是logk的。而counting插入是O(1)的。所以一个是nlogk一个是n,当然不一样。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表