发新帖我要提问
返回列表
打印

数组算法题

[复制链接]
1089|5
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
sinadz|  楼主 | 2013-12-28 21:33 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
数组, 算法, 自然数, 数据
算法题：有1个数组A，里面存放着N个不同的自然数，有1个数组B，里面存在着与A相同自然数的数据，但是存放位置不一样，此外，向B中插入一个与A中数据都不相同的自然数，且插入位置未知，这时B中就有N+1个数据，请使用最快的速度，找到这个不同的自然数。

我个人的想法是先将这两个数组排序，然后用二分(折半)查找来找出那个不同的数出来。但这明显不是最快的方法，请教大家有没有什么快捷的方法可以解决这个问题的？

使用特权

评论回复 赏

相关下载

相关帖子

沙发
gxgclg| | 2013-12-28 21:47 | 只看该作者
如果自然数差值不大的话，用bitset<>记录A ，然后逐个校验B元素也可以，复杂度O(n)

使用特权

评论回复 赏
板凳
comeon201208| | 2013-12-30 23:33 | 只看该作者
我记得有一个叫啥二什么的算法的了，，，就是先将数组一分为二的，在一分为二的，，，如此操作的，效率很高的

使用特权

评论回复 赏
地板
火箭球迷| | 2013-12-31 20:41 | 只看该作者
这道题还是有些难度的

使用特权

评论回复 赏
5楼
smilingangel| | 2014-1-21 22:14 | 只看该作者
就是二分法的效率最高的啊

使用特权

评论回复 赏
6楼
angerbird| | 2014-1-25 15:05 | 只看该作者
是啊，二分法的效率是非常高的

使用特权

评论回复 赏
返回列表
发新帖 我要提问
高级模式
B Color Image Link Quote Code 收费 Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

sinadz

304

主题

2313

帖子

0

粉丝