📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 两个排序数组中求第k大的sum(a+b)

 
🔗
jiebour 2015-7-17 00:20:17 | 只看该作者
全局:
本帖最后由 jiebour 于 2015-7-17 01:30 编辑
zhuli19901106 发表于 2015-7-16 23:00
这不是选取两数组合并后第K小的数,而是选取两数组元素两两相加,组成的N*M个和中的第k小的那个。
并不 ...

你把俩数组组成一个矩阵不就行了? 组成的矩阵中(i, j) 表示A[i] + B[j]的和.若K很小的话,为什么不是 k * lgk
回复

使用道具 举报

🔗
zhuli19901106 2015-7-17 01:28:18 | 只看该作者
全局:
本帖最后由 zhuli19901106 于 2015-7-17 01:43 编辑
jiebour 发表于 2015-7-17 00:20
你把俩数组组成一个矩阵不就行了? 组成的矩阵中(i, j) 表示A + B[j]的和

哦,明白了。你的思路是对的。用最小堆每次选一个出来,选K次,对吧?k很小则是k * log(k),k很大则是k * log(n),因为堆里至多有n个元素,好比n个表头。这个思路比我的代码更直观,不过最小堆要自定义比较符就是了。
回复

使用道具 举报

🔗
mgccl 2015-7-17 23:00:00 | 只看该作者
全局:
O(k)时间的sorted matrix selection就可以了的.  因为A和B已经是sorted.
http://www.chaoxuprime.com/posts ... -sorted-matrix.html
回复

使用道具 举报

🔗
xjbTalk 2015-7-19 04:53:12 | 只看该作者
全局:
danielgao 发表于 2011-5-7 01:58
回复 1# wwwyhx

莫非我理解错了,为啥我觉得这题是O(K)的,

第一反应和你一样,但是我想了个例子,这个方法就不能用了。
A: 1 2 3 5 6
B: 1 2 2 2 6
Sum(a+b): 2, 3, ,3, 4, 4, 4, 5, 5, 5, 7, 8, 8, 8, 8, 9, 11, 12
然后这么做就不行了。。。你试着跑一遍k >= 4的情况
回复

使用道具 举报

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

本版积分规则

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