随笔档案(496)

题目：1 ~ 1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来，不用辅助存储空间，能否设计一个算法实现？

姑且令该数组为int[] a

解法1：数组累和 - （1+2+3+...+.. + 999 + 1000）= 所求结果

public int find(int[] a) {

    int t = 1000 * (1000 + 1) / 2; // 1 ~ 1000的累和
    int sum = 0;
    for(int i = 0;i < a.length;i++) {
        sum += a[i];
    }
    return (sum - t);
}

解法2：异或

将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。

但是这个算法虽然很简单，但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。
首先是异或运算满足交换律、结合律。
所以，1^2^...^n^...^n^...^1000，无论这两个n出现在什么位置，都可以转换成为1^2^...^1000^(n^n)的形式。

其次，对于任何数x，都有x^x=0，x^0=x。
所以1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000（即序列中除了n的所有数的异或）。

令，1^2^...^1000（序列中不包含n）的结果为T
则1^2^...^1000（序列中包含n）的结果就是T^n。
T^(T^n)=n。
所以，将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。

public int find(int[] a) {
    int t1 = 0;
    int t2 = 0;
    for(int i = 0;i < a.length;i++) {
        t1 ^= a[i];
    }

    for(int i = 1;i <= 1000;i++) {
        t2 ^= i;
    }
    return (t1 ^ t2);
}

遗留问题：如果放入数组a中的数为：1000个不连续且互不相同的数(设其组成的数组为n) + 重复数(取自数组n)，又如何求取这个重复数呢，要保证算法的效率哦

参考：

http://www.cnblogs.com/myqiao/archive/2009/07/21/1528156.html

http://www.cnblogs.com/myqiao/archive/2009/07/22/1528271.html