Chinaunix

标题: 出道题目给大家玩玩 , [打印本页]

作者: benjiam 时间: 2009-07-18 15:12
标题: 出道题目给大家玩玩 ,
一个数组 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 编辑 ]

作者: jamesr 时间: 2009-07-18 21:12
提示: 作者被禁止或删除内容自动屏蔽

作者: aaaaa5aa 时间: 2009-07-18 21:29
没看懂题，数组长度为N，数值为 1-2^32.
到底是哪个数值，全部的？

作者: jamesr 时间: 2009-07-18 21:30
提示: 作者被禁止或删除内容自动屏蔽

作者: liuyuanyang 时间: 2009-07-19 01:05
没看懂问题～～～～

作者: emacsnw 时间: 2009-07-19 02:36

原帖由 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 时间: 2009-07-19 05:09
标题: 回复 #6 emacsnw 的帖子
厉害原来是这个意思第一题全部异或起来我算是2^32啊？

作者: aaaaa5aa 时间: 2009-07-19 16:03

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

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

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

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

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

作者: benjiam 时间: 2009-07-19 20:15
嘿嘿,

作者: yecheng_110 时间: 2009-07-20 13:36
设乱序后的数组为a1
1、设取出的数字为x
x=n*(1+2^32)/2 - a1[0] - a1[1] - ... - a[n-2]

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)