网站建设如何不被忽悠/seo网站推广经理

题目描述

1-1000这一千个数放在含有1001个元素的数组中，只有唯一的一个元素重复，其它均只出现依次。设计一个算法，将它找出来。
要求：

1. 每个数组元素只能访问一次
2. 不使用辅助存储空间
   题意分析：
   1000个数中只有一个是重复的，我们要想办法把他找出来，最直观的想法就是双重循环，依次判断这一千个数哪个是重复的，但是！这种方法显然不满足“每个数组元素只能访问一次”的要求。这个办法不行，pass。还有一个比双重循环稍微改进一点的方法，就是在创建一个数组，然后遍历原数组，把1-1000中每个数出现的次数都记录到新数组中，再遍历这个新数组，找出那个出现次数为2的元素即可。然而，这个方法也不满足题意，它违背了“不使用辅助存储空间”的要求，pass。那该怎么办呢？
   没错！就是位运算

那么解决本题需要用到哪些位运算的技巧？

1. 一个数A与0进行异或运算得到的结果是A本身，即：A^0=A
2. 一个数A与它本身进行异或运算将得到0,即：A^A=0

所以，我们直接把数组中的所有数字进行异或运算，即：1异或2异或3^4异或5异或6…异或1000，这样，所有单个的数就被保留了下来，而重复的数会被消除掉，比如说：1异或2异或2异或3，最后的结果就是1异或3（具体1异或3的结果是2，但是我们不考虑，本题不涉及这个问题）。好，我们已经找到这个数了，而且也满足题目的俩个要求。
哎？不对，我都把它给消除了，怎么输出它呢？

所以简单的把数组中的元素都异或显然是行不通的，这就没办法了吗？当然不是。
我们再重新看一下这俩条性质
1. 一个数A与0进行异或运算得到的结果是A本身，即：A^0=A
2. 一个数A与它本身进行异或运算将得到0,即：A^A=0
其实我们很容易就可以推出：A异或A异或A=A
因为前俩个A异或等于0，0再和A异或得到A。
那么，这道题就有办法了！
我们把数组中的元素异或之后，再与1到1000异或一次，这样原来不重复的数，现在有俩个，就直接消除掉了，而原来重复的数字，现在有三个，其中俩个消除了，最终结果只剩下那个重复的数。

代码实现

代码很简单，写出来就没意思了，但是又不能不写，不写没人给我点赞/(ㄒoㄒ)/~~

import java.util.Random;public class testdemo {public static void main(String[] args) {int[] a = testArry();//输出这个数组for(int i=0;i<1001;i++){System.out.print(a[i]+" ");}System.out.println();int result=0;//用来存放最终结果//先让数组中的所有元素都相互异或for(int i=0;i<1001;i++){result=result^a[i];}//再与1~1000异或一次for(int i=1;i<=1000;i++){result=result^i;}System.out.println(result);}/*首先创建一个方法用来生成一个符合题目要求的数组这部分可以不看，只看主方法*/public static int[] testArry() {int n = 1001;Random r = new Random();int[] a = new int[n];int i = 0;//前1000位放0到1000for (i = 0; i <= n - 2; i++) {a[i] = i + 1;}//在第1000位放一个随机数，随机数取值为[1,1000]a[n - 1] = r.nextInt(n - 1) + 1;//将最后一个数随机地与前1000中的某个数交换i = r.nextInt(n - 1);int temp = 0;temp = a[i];a[i] = a[n - 1];a[n - 1] = temp;return a;}
}

看完这篇，做一道类似的练习题吧：玩转位运算-经典例题1（续）