出道题目给大家玩玩 ,

benjiam

一个数组 a[n]，数组长度为n， 已知  n = 2^32.  
数值为 1,2, 3.....2^32.
即
a[0] =1
a[1] =2
.....
   

随机乱序整个数组，  取出乱序后数组的最后的一个数字。



1 找出这个数字， 求算法


2 取掉最后的2个数字， 求算法

[ 本帖最后由 benjiam 于 2009-7-18 22:15 编辑 ]

aaaaa5aa

没看懂题，数组长度为N， 数值为 1-2^32.
到底是哪个数值，全部的？

liuyuanyang

没看懂问题～～～～

emacsnw

原帖由 benjiam 于 2009-7-17 23:12 发表
一个数组 a[n]，数组长度为n， 已知  n = 2^32.  
数值为 1,2, 3.....2^32.
即
a[0] =1
a[1] =2
.....
   

随机乱序整个数组，  取出乱序后数组的最后的一个数字。



1 找出这个数字， 求算法 ...

所有剩下的数字异或起来就是缺少的那个数字。因为要是一个都不缺的话，全异或起来是0.

少两个的话，求剩下的数的平方和X，全加起来得到Y。然后求解方程（设缺少的两个数是a和b）：
a*a + b*b = n(n+1)(2n+1)/6 - X
a + b = n(n+1)/2 - Y
可能具体公式数字有点出入，自己考证一下就行。

vbs100

厉害 原来是这个意思  第一题全部异或起来我算是2^32啊？

aaaaa5aa

原帖由 emacsnw 于 2009-7-19 02:36 发表


所有剩下的数字异或起来就是缺少的那个数字。因为要是一个都不缺的话，全异或起来是0.

少两个的话，求剩下的数的平方和X，全加起来得到Y。然后求解方程（设缺少的两个数是a和b）：
a*a + b*b = n(n+1)( ...

不是很认同LS的方法，那样是找不出那个数的

我提供一种思路，把原来的数组保存，然后每个都减去现在的数组，组成一个新的数组，最后加起来的值就是缺少的值

benjiam

嘿嘿,

yecheng_110

设乱序后的数组为a1
1、设取出的数字为x
x=n*(1+2^32)/2 - a1[0] - a1[1] - ... - a[n-2]