题解 | #找出重复的数#

题意整理

给定一个长度为n+1的序列，包含1到n之间的数。
有一个数重复了，找出重复的数。

方法一（数学）

1.解题思路

先计算出序列中所有数字的和。
然后计算1到n所有数字的和。
由于序列中有一个重复了，所以序列和中多算了一次，从序列和中减去1到n所有数的和，即时那个重复的数字。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a int一维数组 
     * @return int
     */
    public int search (int n, int[] a) {
        //统计所有数之和
        int sum=0;
        for(int i=0;i<=n;i++){
            sum+=a[i];
        }
        //从sum中减去1到n的累加和，即是重复的数字
        return sum-n*(n+1)/2;
    }
}

3.复杂度分析

时间复杂度：只需一次线性遍历，所以时间复杂度为 $O(n)$ 。
空间复杂度：不需要额外的空间，所以空间复杂度为 $O(1)$ 。

方法二（异或）

1.解题思路

先计算1到n中所有数字的异或（记为m）。
然后计算出序列中所有数字的异或（记为res）。
如果两个相同的数字异或，则所有位都会抵消，从而变为0。所以m中保留着1到n所有数字的异或，而res中会消去重复出现的那个数字，保留着1到n中除了重复数字之外所有数字的异或，将m和res再次异或，则可以消去只出现一次的那些数字，从而留下重复出现的数字。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a int一维数组 
     * @return int
     */
    public int search (int n, int[] a) {
        //统计1到n所有数字间的异或
        int m=0;
        //统计a数组中所有数字间的异或
        int res=a[0];
        for(int i=1;i<=n;i++){
            m=m^i;
            res=res^a[i];
        }
        //将res和m再次异或，重复数字只在m中出现一次，在res中被消去
        return res^m;
    }
}

3.复杂度分析

时间复杂度：只需一次线性遍历，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。