【试题***】找出重复的数字

找出重复的数字

题目

一组无序的自然数集合，由0,1,2... ...,n的数字和一个的数字X（X>=0 && X<=n）组成，请从集合中找出这个重复数字X。

解题思想

使用异或的特性：0^任意数=任意数，任意数^任意数=0，异或计算的无序性（即1^2^3 = 2^3^1）

import java.util.*;
public class Main {

    public static void main(String[] args) {
        //System.out.println("请输入数字：");
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> arr =  new ArrayList<Integer>();
        while(sc.hasNext())
        {
            arr.add(sc.nextInt());
        }
        //System.out.println(arr);
        int x = 0;
        for(int i = 0; i < arr.size()-1; i++){
            x ^= i;
        }
        for(int i = 0; i < arr.size(); i++){
            x ^= arr.get(i);
        }

        System.out.print(x);
    }
}