13
回答
一道逻辑题:我拿走了哪个数
滴滴云服务器,限时包月0.9元,为开发者而生>>>   

原文链接:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html

作者:@baiyanhuang


有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?

相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记录下来。 说是逻辑题,其实也算是一道算法题,同事先讲了下他被面试中的思维过程:

  1. 先把 10000 个数相乘,然后再将拿走一个数之后的 9999 个数相乘,两者相除即可。

    这个算法是正确的,但是会有两个潜在的问题:

    • 如此多的数相乘,其范围必然会超出系统提供的数据类型支持,当然你可以实现自己的大数表示的算法,但那样性能必然有影响。
    • 假设扩展一下题目,提供的数组中有 0 的话,乘法就不可用了。
  1. 针对前面提出的问题,同事想到了使用加法,先求出 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. 异或的速度要快于加法

扩展一下题目,如果提供的不是整数,而是浮点数,会有问题吗? 当然没有,因为是在位级别上操作,无论是整数还是浮点数,在这个算法看来,都是一堆位,处理起来没有什么差别。

再扩展一下题目,如果提供的数本身就超出了内置类型的表示范围,如在 1 到 2^128,该如何处理? 这个问题是在写这篇文章的过程中想到的,暂时没有好的办法。

<无标签>
举报
justjavac
发帖于3年前 13回/503阅
共有13个答案 最后回答: 3年前

为什么不直接加 和(是 50005000 这个数字并不大 而且不会越界吧)

再减呢 

大概算了下 怎么都要 n-1次计算

至于楼上说的 二分 明显是在已经排序号的情况下  

--- 共有 1 条评论 ---
拉风的道长赞!我也是认为直接加再减就行了。 3年前 回复
看到乘法的时候我就笑了,你遍历一遍乘的时候,顺便检查下跟i是不是相等不就知道了吗。。。

其实不考虑空间的话 还有个办法,  创建一个 数组, 数组里面全是0 如果有就放1 最后为0 的那个的下标就是了~!

还有,加法会越界,减法就好了,从1000 个里面取数去减 999里面的数,每次操作之后 如果大于0  则继续减999 里面的数,如果小于0 就从1000 里面拿数出来相加 然后操作完之后再判断

这种问题,其实是在问在某种特定的条件下才有意义,而这种特定条件无非就是时间和空间,楼上什么都不考虑或考虑不周的人,应该是对这道题的误解。

引用来自“just4scala”的评论

这种问题,其实是在问在某种特定的条件下才有意义,而这种特定条件无非就是时间和空间,楼上什么都不考虑或考虑不周的人,应该是对这道题的误解。
考虑很周啊,不就10000个数?能有多大计算压力?放着机器,费人脑子想算法才是毫无必要。
顶部