算法学习|题目：找出唯一成对的数(基于Java)

本文主要是介绍算法学习|题目：找出唯一成对的数(基于Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：找出唯一成对的数

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

分析：运用位运算

知识补充：
1.A ^ A = 0
2.A ^ 0 = A
3.A ^ A ^ B ^ C ^ C = A ^ A ^ B ^ C ^ C = 0 ^ B ^ 0 = B
4.由以上可得偶数个相同的数异或等于0；奇数个相同的数异或等于它本身，欲得到出现两次的数，使用含有1001个元素的原数组arr(1 ~ 1000加上1个重复数)与1 ~ 1000相异或，则目标数出现三次，其余数出现两次，结果直接得到目标重复数

代码

import java.util.Random;
import java.util.Arrays;public class Demo{public static void main(String[] args) {int N = 1001;int[] arr = new int[N];	//定义一个可存放N个元素的数组//将1到N-1依次存入数组for(int i = 0;i < N-1;i++) {arr[i] = i + 1;}//获取1到N-1的随机数，并将此数赋值给数组最后一个元素arr[arr.length - 1] = (new Random().nextInt(N - 1)) + 1;	//nextInt(n)方法可以得到[0,n)的整数//获取0到N-1的随机索引int index = new Random().nextInt(N);//将数组arr最后一个元素(随机数)的索引值变换为某随机索引值int temp = arr[index];arr[index] = arr[arr.length - 1];arr[arr.length - 1] = temp;//得到0^1^2···^(N-1)并将结果赋值给xint x = 0;for(int i = 1;i < N;i++) {x ^= i;}//x依次与arr数组中的元素异或，结果赋值给xfor(int i = 0;i < N;i++) {x ^= arr[i];}//遍历数组System.out.println(Arrays.toString(arr));//输出重复值System.out.println("重复的数为：" + x);}
}

补充方法：若可以使用辅助存储空间

import java.util.Random;
import java.util.Arrays;public class Demo{public static void main(String[] args) {int N = 1001;int[] arr = new int[N];	//定义一个可存放N个元素的数组//将1到N-1依次存入数组for(int i = 0;i < N-1;i++) {arr[i] = i + 1;}//获取1到N-1的随机数，并将此数赋值给数组最后一个元素arr[arr.length - 1] = (new Random().nextInt(N - 1)) + 1;	//nextInt(n)方法可以得到[0,n)的整数//获取0到N-1的随机索引int index = new Random().nextInt(N);//将数组arr最后一个元素(随机数)的索引值变换为某随机索引值int temp = arr[index];arr[index] = arr[arr.length - 1];arr[arr.length - 1] = temp;//方法2：使用辅助空间//定义一个辅助数组helpint[] help = new int[N];//将arr数组中的值依次作为help数组的索引，当从arr中获取一个值作为help索引k时，在该索引下的help自增1//则重复出现的那个arr数组元素值是help数组中值为2的索引值for(int i = 0;i < N;i++) {help[arr[i]]++;}//遍历数组System.out.println(Arrays.toString(arr));//输出该重复值for(int i = 0;i < N;i++) {if(help[i] == 2) {System.out.println("重复的数为：" + i);}}}
}