如何找数组中唯一成对的数

题目

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来

答案

public class T1_2 {
    public static void main(String[] args) {
        //构造数组
        int N = 1001;
        int[] arr = new int[N];
        //前1000位按顺序填入
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i]=i+1;
        }
        //最后一个数，是随机数
        arr[arr.length-1] = new Random().nextInt(N-1)+1;
        //找一个随机下标
        int index = new Random().nextInt(N);
        //调用方法，将随机数放到随机下标处
        swap(arr, index, arr.length-1);
        //重新获取一个随机数填补最后一位的空缺
        arr[arr.length-1]=new Random().nextInt(N);
        //打印数组，方便观察
        System.out.println(Arrays.toString(arr));


        //开始找出唯一成对的数
        /**
         * 思路：
         *      相当于将数组中的内容和1-1000连续异或
         *      即重复的那个数会有三个，其他的数有两个
         *      因为一个数异或他本身等于0，所以最后只剩下重复的那个数
         */
        int x1 = 0;//存储结果
        //第一遍异或，1-1000的连续异或
        for (int i = 1; i <= N-1; i++) {
            x1=(x1^i);
        }
        //此时x1为1-1000连续异或的结果，用于在下面的循环中消除重复

        //第二遍异或，消除重复
        for (int i = 0; i < N; i++) {
            x1=x1^arr[i];
        }
        //数组中只有重复的数是两个，其他数字均为1个
        //与第一遍的结果进行连续异或，相当于不重复的数各有两个，而重复的数会出现三个
        //所以重复的数会剩最后一个
        System.out.println(x1);

        
    }
    public static void swap(int[] array,int x,int y){
        int xx = array[x];
        int yy = array[y];
        array[x] = yy;
        array[y] = xx;
    }
}