p****o 发帖数: 46 | 1 数组a[]={1,2,3,...,n}, 一个数missing
求这个数。
如果求和,有人说会overflow.
有人说用xor,
可是如果用xor, sum=sum+a[i]^i, 问题是这个i也不对齐阿。
a[]={1,2,4,5}, 这个是4^3。
难到用相邻两个数xor?但是前提是这个数组必须是sorted.
不求和的办法是什么? | P*******e 发帖数: 1353 | 2 binary search
【在 p****o 的大作中提到】 : 数组a[]={1,2,3,...,n}, 一个数missing : 求这个数。 : 如果求和,有人说会overflow. : 有人说用xor, : 可是如果用xor, sum=sum+a[i]^i, 问题是这个i也不对齐阿。 : a[]={1,2,4,5}, 这个是4^3。 : 难到用相邻两个数xor?但是前提是这个数组必须是sorted. : 不求和的办法是什么?
| c****s 发帖数: 241 | 3 您没有明白原来的题目要求。
求和的方法是:sum=1+2+3+...+n, and then sum-=a[i] for i=1,..n-1,最后sum就是
你要那个数了。
XOR的方法是:t ^= i for i=1,...,n and then t ^= a[i] for i=1,..,n-1,最后t就是
你要的那个数了
【在 p****o 的大作中提到】 : 数组a[]={1,2,3,...,n}, 一个数missing : 求这个数。 : 如果求和,有人说会overflow. : 有人说用xor, : 可是如果用xor, sum=sum+a[i]^i, 问题是这个i也不对齐阿。 : a[]={1,2,4,5}, 这个是4^3。 : 难到用相邻两个数xor?但是前提是这个数组必须是sorted. : 不求和的办法是什么?
| p****o 发帖数: 46 | 4 ok. 我知道了。
就是
【在 c****s 的大作中提到】 : 您没有明白原来的题目要求。 : 求和的方法是:sum=1+2+3+...+n, and then sum-=a[i] for i=1,..n-1,最后sum就是 : 你要那个数了。 : XOR的方法是:t ^= i for i=1,...,n and then t ^= a[i] for i=1,..,n-1,最后t就是 : 你要的那个数了
| c*********n 发帖数: 1057 | 5
~~~~~~~~~~~~~~~~~~~~这样的话overflow是不是也没关系啊?
就是
【在 c****s 的大作中提到】 : 您没有明白原来的题目要求。 : 求和的方法是:sum=1+2+3+...+n, and then sum-=a[i] for i=1,..n-1,最后sum就是 : 你要那个数了。 : XOR的方法是:t ^= i for i=1,...,n and then t ^= a[i] for i=1,..,n-1,最后t就是 : 你要的那个数了
| c***g 发帖数: 472 | 6 对这个overflow一直有一个疑问, 如果先把1到n全部加起来,n足够大, 肯定有overflow
的问题
可以这样做么? 加一个减一个, 是不是就没有overflow了?
S=0
for i = 1 to n-1
S += i - a[i]
S += n
return S;
【在 p****o 的大作中提到】 : 数组a[]={1,2,3,...,n}, 一个数missing : 求这个数。 : 如果求和,有人说会overflow. : 有人说用xor, : 可是如果用xor, sum=sum+a[i]^i, 问题是这个i也不对齐阿。 : a[]={1,2,4,5}, 这个是4^3。 : 难到用相邻两个数xor?但是前提是这个数组必须是sorted. : 不求和的办法是什么?
|
|