异或
——如何找数组中唯一成对的那个数（数组特殊）
1-1000这一千个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。 每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助储存空间，设计一个算法实现.
package LanQiao; import java.util.Random; /** * @Author: Mo * @Date: 2021/1/18 21:11 */ public class FindD { public static void main(String[] args) { int N = 1000; int []arr = new int[N]; for (int i = 0;i< arr.length-1;i++){ arr[i]=i+1; System.out.print(arr[i]+" "); } //最后一个数，是随机数 arr[arr.length-1]=new Random().nextInt(N-1); System.out.println(arr[arr.length-1]); int x1 = 0; for (int i = 0; i < N; i++) { x1 = x1^arr[i]; } for (int i = 1; i < N; i++) { x1 = x1^i; } System.out.println(x1); } }
原理
A^A=0
B^0=B
A ^ A ^ B ^ C ^ C:即可消除重复的，保留单个的
(1 ^ 2 ^ 3 ^ … ^ K ^ … ^ 1000 ^ K) ^ (1 ^ 2 ^ 3 ^ … ^ 999 ^ 1000) = K
如果数组中其他数无法确定或方便的表示，则需要辅助储存空间暴力破解
int[] arry = new int[N]; for (int i = 0; i < N; i++) { arry [arr[i]]++; } System.out.println(); for (int i = 0; i < N;i++){ if (arry[i] ==2) { System.out.println(i); }
