题目:
1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助存储空间，能否设计一个算法实现？
刚开始的想法是，直接排序，然后相邻的元素进行对比不就好了？ 但后来发现没有这么简单，题目要求，每个数组元素只能访问一次。
位运算技巧：a^a = 0 a^0 = a
题解：根据上面的式子，根据相同的数相与为0,0与任何数与为任何数可以求得
public static void main(String[] args) { int N = 1001; int x = 0; int a [] = new int [N]; for(int i = 0;i<a.length-1;i++){ a[i] = i+1; } a[a.length-1] = new Random().nextInt(N-1)+1; int index = new Random().nextInt(a.length-1); swap(a[index],a[a.length-1]); for(int i =1;i<=a.length-1;i++){ x = x^i; } for(int i =0;i<a.length;i++){ x = x^a[i]; } System.out.println(x); } public static void swap(int a,int b){ a=a^b; b=a^b; a=a^b; }
题解二：暴力求解，将一个数组中的数作为另一个数组的索引通过数组大小来获取所求值
public static void main(String[] args) { int N = 1001; int x = 0; int a [] = new int [N]; for(int i = 0;i<a.length-1;i++){ a[i] = i+1; } a[a.length-1] = new Random().nextInt(N-1)+1; int index = new Random().nextInt(a.length-1); swap(a[index],a[a.length-1]); // 直接暴力解法 int [] h = new int [N]; for(int i = 0;i<a.length;i++){ h[a[i]]++; } for(int i =0;i<a.length;i++){ if(h[i] == 2){ System.out.println(i); break; } } } public static void swap(int a,int b){ a=a^b; b=a^b; a=a^b; }
