查看: 16486|回复: 43
收起左侧

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

  |只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:google : 最小窗口问题
下一篇:Microsoft : Find pivot
mgccl 2015-7-17 23:00:00 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   95% (21)
 
 
4% (1)    👎
O(k)时间的sorted matrix selection就可以了的.  因为A和B已经是sorted.
http://www.chaoxuprime.com/posts ... -sorted-matrix.html
回复

使用道具 举报

jiebour 2015-7-16 22:08:14 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   72% (24)
 
 
27% (9)    👎
这个题其实就是leetcode里面merge K sorted list的变体,仔细想想就明白了。

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

使用道具 举报

danielgao 2011-5-7 01:58:17 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (86)
 
 
3% (3)    👎
回复 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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-5-7 00:40:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
本帖最后由 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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
本帖最后由 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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (86)
 
 
3% (3)    👎
回复  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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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