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

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

 
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
就是两个数组A,B. 是排好序的,a是A中的元素,b是B中的元素,求第k大的sum(a+b)
穷举法是O(n^2) 给出最优解,给出时间空间复杂度

上一篇:google : 最小窗口问题
下一篇:Microsoft : Find pivot
推荐
mgccl 2015-7-17 23:00:00 | 只看该作者
全局:
O(k)时间的sorted matrix selection就可以了的.  因为A和B已经是sorted.
http://www.chaoxuprime.com/posts ... -sorted-matrix.html
回复

使用道具 举报

推荐
jiebour 2015-7-16 22:08:14 | 只看该作者
全局:
这个题其实就是leetcode里面merge K sorted list的变体,仔细想想就明白了。

K远远小于M,N(分别为A,B数组的长度)的话,那么复杂度就是 K*lgK。
若不是,复杂度就是K*lg(Min(M, N))
回复

使用道具 举报

推荐
danielgao 2011-5-7 01:58:17 | 只看该作者
全局:
回复 1# wwwyhx

莫非我理解错了,为啥我觉得这题是O(K)的,
假设是从大到小排列,从小到大就是反个方向而已
最大的肯定是a[1]+b[1]

然后维持两个指针i = 1, j =1
如果a(i) + b(j+1) > a(i+1) + b(j) 就++j,否则++i
计数输出第k个就好
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-6 16:53:50 | 只看该作者
全局:
我好想找了个O(logn)的,不知道对不对
回复

使用道具 举报

🔗
Imbalism 2011-5-7 00:40:43 | 只看该作者
全局:
1.找出r, 使得r ^ 2 < k 且 (r + 1 )^2 > k.  a, b 肯定不在A[1...r]和b[1...r]中. 这样的组合有r^2个
2. 如果剔除掉上面的A[1...r]与B[1...r], 问题变成找出排名为k - r^2 的和
现在看A[r+1]与B[r+1], A[r+1] + B[1], A[1] + B[r + 1]  肯定是最小的两个和.
A[r + 1] + B[2], A[2] + B[r + 1] 是第三小与第四小的和.
这样A[r + 1] + B[k - r^2], A[k - r^2] + B[r + 1]中就能找到k - r^2的和

1的复杂度是O(logn) 2是O(1), 不知道对不对
回复

使用道具 举报

🔗
darksteel 2011-5-7 01:38:45 | 只看该作者
全局:
回复 3# Imbalism

好像是有问题的,因为你无法保证a, b 肯定不在A[1...r]和b[1...r]中,最简单的例子:
A: 4, 3, 2, 1
B: 9, 5, 2, 1
k = 5
答案应该是4+5,你的方法应该得不出这个答案,希望我没理解错~

这题我应该见过的,至少有O(nlogn)的方法。
回复

使用道具 举报

🔗
Imbalism 2011-5-7 02:01:24 | 只看该作者
全局:
本帖最后由 Imbalism 于 2011-5-7 02:11 编辑
回复  Imbalism

好像是有问题的,因为你无法保证a, b 肯定不在A[1...r]和b[1...r]中,最简单的例子:
A: 4, 3, 2, 1
B: 9, 5, 2, 1
k = 5
答案应该是4+5,你的方法应该得不出这个答案,希望我没理解错~

这题我应该见过的,至少有O(nlogn)的方法。
darksteel 发表于 2011-5-7 01:38


恩, 想错了... 再想想
回复

使用道具 举报

🔗
darksteel 2011-5-7 02:15:19 | 只看该作者
全局:
本帖最后由 darksteel 于 2011-5-7 02:18 编辑

回复 5# danielgao
你的想法跟那种解法有点类似,但有一点问题:每个位置上可能的candidates不止有两个,或者说i,j不会退的话会漏掉candidate。假设最大的是a[1]+b[1],然后是a[1]+b[2],在你的方法中下一个数只能在a[1]+b[3]和a[2]+b[2]中选,但完全可能是a[2]+b[1]。
一种可行的解法是用堆,最开始是a(1)+b(1)在堆里,每次把堆顶元素a(i)+b(j)拿出来,然后把a(i+1)+b(j)和a(i)+b(j+1)放入堆中,这样可以保证不漏掉元素。这个不是我想出来的,网上听人说的。
回复

使用道具 举报

🔗
danielgao 2011-5-7 04:54:19 | 只看该作者
全局:
回复  danielgao
你的想法跟那种解法有点类似,但有一点问题:每个位置上可能的candidates不止有两个,或者说i,j不会退的话会漏掉candidate。假设最大的是a[1]+b[1],然后是a[1]+b[2],在你的方法中下一个数只能在a[1]+b[3]和a[2]+b[2]中选,但完全可能是a[2]+b[1]。
一种可行的解法是用堆,最开始是a(1)+b(1)在堆里,每次把堆顶元素a(i)+b(j)拿出来,然后把a(i+1)+b(j)和a(i)+b(j+1)放入堆中,这样可以保证不漏掉元素。这个不是我想出来的,网上听人说的。
darksteel 发表于 2011-5-7 02:15


用堆得确能用来保存前k大数,但是你i和j如何移动呢?
回复

使用道具 举报

🔗
darksteel 2011-5-7 08:10:31 | 只看该作者
全局:
回复 8# danielgao
初始a(1)+b(1)在堆里,然后每次从堆上弹出一个元素,假设它是a(i)+b(j),那就把a(i+1)+b(j)和a(i)+b(j+1)加入堆中。每次加入堆中的元素依赖于当前堆顶的元素。需要用一些手段保证不加入重复的元素。
据说是借鉴了杨氏矩阵的思想。我不能直接看出正确性,希望有人明白的话能说说为什么这样是对的,为什么不会漏掉candidates?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-7 20:55:43 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-5-7 21:31 编辑

额,搞错了,无视我吧
回复

使用道具 举报

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

本版积分规则

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