- justjavac
- 等级:
- 性别:
- 文章: 42
- 积分: 130
- 来自: 天津
|
原文链接:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html
作者:@baiyanhuang
有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?
相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记录下来。 说是逻辑题,其实也算是一道算法题,同事先讲了下他被面试中的思维过程:
-
先把 10000 个数相乘,然后再将拿走一个数之后的 9999 个数相乘,两者相除即可。
这个算法是正确的,但是会有两个潜在的问题:
- 如此多的数相乘,其范围必然会超出系统提供的数据类型支持,当然你可以实现自己的大数表示的算法,但那样性能必然有影响。
- 假设扩展一下题目,提供的数组中有 0 的话,乘法就不可用了。
-
针对前面提出的问题,同事想到了使用加法,先求出 10000 个数的和,再减去 9999 个数的和。
这样数据不会溢出,而且加法的效率比乘法也要高很多,即使数据中包含 0,也没有任何问题。
然后就过关了,自己回去之后思考了一下,觉得还可以扩展,假设所有的数加起来之后仍然会溢出,那该如何处理,比如从 1 到 (2^64-1),于是想到了位操作,与、或,异或中,要数异或最为神奇,代入一看,果然合适: 先将所有的数异或起来,然后将拿走一个数之后的数异或起来,两者结果再异或,便是拿走的那个数。
我用 a,b,c,d 4 个数来做演示,因为异或符合结合律和交换律(你可以用 0,1 试一下),于是:
a^b^c^d = (a^b^c)^d
d = (a^b^c^d)^(a^b^c)
此处用异或的好处在于
- 不会溢出
- 异或的速度要快于加法
扩展一下题目,如果提供的不是整数,而是浮点数,会有问题吗? 当然没有,因为是在位级别上操作,无论是整数还是浮点数,在这个算法看来,都是一堆位,处理起来没有什么差别。
再扩展一下题目,如果提供的数本身就超出了内置类型的表示范围,如在 1 到 2^128,该如何处理? 这个问题是在写这篇文章的过程中想到的,暂时没有好的办法。
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
|
返回顶楼 |
|
|
- rmzdb
- 等级: 初级会员
- 性别:
- 文章: 21
- 积分: 80
- 来自: 合肥
|
楼主 你这个1到10000个数是有序递增的么? 如果是的,最简单的办法就是求相邻差是否为1 仅此而已。很多考官喜欢这样来问 数据库的 sql语句的。
|
返回顶楼 |
|
|
- jahu
- 等级: 初级会员
- 性别:
- 文章: 59
- 积分: 80
- 来自: 长沙
|
需要这么复杂吗? 使用链表的数据格式, 用二分就简单的能找到这个数了,
|
返回顶楼 |
|
|
- rmzdb
- 等级: 初级会员
- 性别:
- 文章: 21
- 积分: 80
- 来自: 合肥
|
jahu 写道 需要这么复杂吗?
使用链表的数据格式,
用二分就简单的能找到这个数了,
你真搞笑 二分? 都不知道寻找的目标 怎么二分啊
|
返回顶楼 |
|
|
- zhang_guiren
- 等级: 初级会员
- 性别:
- 文章: 3
- 积分: 30
- 来自: 北京
|
rmzdb 写道 jahu 写道 需要这么复杂吗?
使用链表的数据格式,
用二分就简单的能找到这个数了,
你真搞笑 二分? 都不知道寻找的目标 怎么二分啊 二分法可以,第一次取出1-5000个数字,放入数组,看其长度是否等于5000,不等于则继续二分1-5000,等于则取5000-10000放入数组,重复上述过程
|
返回顶楼 |
|
|
- rmzdb
- 等级: 初级会员
- 性别:
- 文章: 21
- 积分: 80
- 来自: 合肥
|
zhang_guiren 写道 rmzdb 写道 jahu 写道 需要这么复杂吗?
使用链表的数据格式,
用二分就简单的能找到这个数了,
你真搞笑 二分? 都不知道寻找的目标 怎么二分啊
二分法可以,第一次取出1-5000个数字,放入数组,看其长度是否等于5000,不等于则继续二分1-5000,等于则取5000-10000放入数组,重复上述过程
这样做 也是基于连续数字的 前提:就是中间值一定是前一半 后一般的 这样确实可以。
|
返回顶楼 |
|
|
- jahu
- 等级: 初级会员
- 性别:
- 文章: 59
- 积分: 80
- 来自: 长沙
|
rmzdb 写道 zhang_guiren 写道 rmzdb 写道 jahu 写道 需要这么复杂吗?
使用链表的数据格式,
用二分就简单的能找到这个数了,
你真搞笑 二分? 都不知道寻找的目标 怎么二分啊
二分法可以,第一次取出1-5000个数字,放入数组,看其长度是否等于5000,不等于则继续二分1-5000,等于则取5000-10000放入数组,重复上述过程
这样做 也是基于连续数字的 前提:就是中间值一定是前一半 后一般的 这样确实可以。
谁说要基于连续数字啊,二分,简单下,效率不是最高,但是数据量大之后效率是最高的一个思路
|
返回顶楼 |
|
|
- rmzdb
- 等级: 初级会员
- 性别:
- 文章: 21
- 积分: 80
- 来自: 合肥
|
jahu 写道 rmzdb 写道 zhang_guiren 写道 rmzdb 写道 jahu 写道 需要这么复杂吗?
使用链表的数据格式,
用二分就简单的能找到这个数了,
你真搞笑 二分? 都不知道寻找的目标 怎么二分啊
二分法可以,第一次取出1-5000个数字,放入数组,看其长度是否等于5000,不等于则继续二分1-5000,等于则取5000-10000放入数组,重复上述过程
这样做 也是基于连续数字的 前提:就是中间值一定是前一半 后一般的 这样确实可以。
谁说要基于连续数字啊,二分,简单下,效率不是最高,但是数据量大之后效率是最高的一个思路
你告诉我怎么确定中间值??? 怎么取这个1-5000个数字啊 既然你都是确定是1-5000个数字,为什么长度还不确定是5000呢?
|
返回顶楼 |
|
|
- Function
- 等级: 初级会员
- 性别:
- 文章: 36
- 积分: 90
- 来自: 南京
|
有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个? 答案: 拎起你的领口,快说,拿走了哪个,不说揍死你!丫的
|
返回顶楼 |
|
|
- helin
- 等级:
- 性别:
- 文章: 81
- 积分: 120
- 来自: 北京
|
Function 写道 有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?
答案: 拎起你的领口,快说,拿走了哪个,不说揍死你!丫的
好的,那个数我放在黄浦大道直走第二个路口左转进入无名小道然后穿过一片艹皮寻找第3个垃圾桶,里面有一封信,上面写着下一个目的地...........
|
返回顶楼 |
|
|