唯一成对的数

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

import java.util.Random;
import java.util.Scanner;

public class 唯一成对的数 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//数组大小
        int[] nums = new int[n];
        //按1---(n-1)个数字依次存入数组中
        for (int i = 0; i < n - 1; i++) {
            nums[i] = i + 1;
        }
        //数组最后一个元素用随机数来确定,用来确定哪个数会是成对
        nums[n - 1] = new Random().nextInt(n - 1) + 1;
        //随机一个index下标,用于与最后一个元素交换位置
        int index = new Random().nextInt(n - 1);

        // swap 位置
        int temp = nums[n - 1];
        nums[n - 1] = nums[index];
        nums[index] = temp;

        // foreach 出来看一下数组
        for (int i : nums) {
            System.out.print(i + " ");
        }
        System.out.println();
        /*
            知识点1:任何数异或0等于数本身
            知识点2:数异或自己等于0, 即A^A=0, 可用于消除两两重复的数

            假设 n = 1001 那么就存1到1000的数进数组,最后一个数用于确定哪个数字是一对
            解题思路: A^A^B^C^C = B 可知异或可以消除两两重复的数
            那么,我们题目要求的是,找出两两重复的数,而不是消除它,脑筋急转弯
            我们可以通过 1^2^...k..^1000 ^(1^2^....k......k.^1000)
            那么因为数值1,2,3,....n都成对存在而消除了,但是却有3个k ,
            k^k^k ===>  k^k = 0,0^k = k,这就可以得出结果了
         */
        int result = 0;
        for (int i = 1; i <= n - 1; i++) {
            result ^= i;
        }
        for (int i = 0; i < n; i++) {
            result ^= nums[i];
        }
        System.out.println(result);
    }
}