查看: 2100|回复: 6
收起左侧

Google : 找中数

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

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

上一篇:career cup top150 questions, 4th ed.
下一篇:Anonymous : 求数组中元素为另外两个元素和的最大元素
yxyxyx 2011-5-14 22:29:10 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (851)
 
 
2% (26)    👎
基本和两个排好序的数组合成一个大数组的步骤类似吧,甚至还要简单一点(amax<bmin的时候直接拿来计算就好了,反之亦然)。只不过在第n步的时候(假设一个数组长度为n)停止就好了,另外需要记录第n大的和第n+1大的数。
如果两个数组都是从小到大排的那就是:

float result;
if(a[n] < b[0]) result =(a[n]+b[0])/2;
else if(a[0]>b[n]) result=(a[0]+b[n])/2;
else
{
int ia=0,ib=0;
for(int t=0; t < n; t++)
{
        if(a[ia] < b[ib])  ia++;
        else                   ib++;
}
result =(a[ia]+b[ib])/2;
}
回复

使用道具 举报

bill 2011-5-15 01:17:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
O(n)。 每次对半分,看哪半多哪半少,然后变更问题(如找第x大数)继续递归。
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-15 02:28:27 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

darksteel 2011-5-15 06:10:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 4# wwwyhx
我只能想到(logn)^2的。用二分在A中枚举,对每个值在B里二分找它的位置(找lower_bound),然后根据该元素在整个A和B中所处的位置调整二分的区间
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-15 10:52:44 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

darksteel 2011-5-15 12:45:40 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 6# wwwyhx
仔细想想还真是,很巧妙的方法~
回复

使用道具 举报

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

本版积分规则

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

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