题解 | #找出重复的数#

题目：
在包含 n+1 个数的序列 a 中找出重复的数。序列 a 中包含从 1 到 n 的整数，且只有一个数有重复值。
要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。

方法一：求和
求出1+2+...n=sum的值，计算a数组的和，a数组的和减去sum就得到重复数字

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a int一维数组 
     * @return int
     */
    public int search (int n, int[] a) {
        // write code here
        int sum=0;
        for(int i=0;i<a.length;i++){
            sum+=a[i];
        }
        return sum-(1+n)*n/2;
    }
}

复杂度：
时间复杂度： $O(n)$ ,最多访问n次
空间复杂度： $O(1)$ ,额外变量为常数级
方法二：异或
在数学中，异或的定义即一个元素在集合A或者在集合B中，用韦恩图表示为
图片说明
则异或的性质有A^A=0,A^0=A;则1^2^x^x...^n=1^2...^n^(x^x)=1^2...^n^0=1^2...^n=T（含有重复x）,则1^2...^n（含有一个x）=T^x;则有T^T^x=x,由此得出x

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a int一维数组 
     * @return int
     */
    public int search (int n, int[] a) {
        // write code here
        int y=0;
        int x=a[0];
        for(int i=1;i<a.length;i++){
            x=x^a[i];
            y=y^i;
        }
        return x^y;
    }
}

复杂度：
时间复杂度： $O(n)$ ,最多访问n次
空间复杂度： $O(1)$ ,额外变量为常数级