题解 | #找出重复的数#

思路：

题目很短，主要信息为：

• 序列a中的数字为1到n的整数，只有一个数字重复
• 时间复杂度为 O(n)，额外空间复杂度为 O(1)。

方法一：求和相减

具体做法：
1到n的整数之和为sum=
若a中重复的数字为i，则a中所有数字之和可以表示为a_sum=
这样就能够得到重复的数字为a_sum-sum=i。
图解示例：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a intvector 
     * @return int
     */
    int search(int n, vector<int>& a) {
        // write code here
        int a_sum=0;//a_sum保存序列a中所有数之和
        for(int i=0;i<=n;i++)
        {
            a_sum+=a[i];
        }
        int sum=0;//sum保存1到n整数之和
        for(int i=1;i<=n;i++)
        {
            sum+=i;
        }
        int result=a_sum-sum;//得到重复值
        return result;
    }
};

复杂度分析：

• 时间复杂度： ,一层遍历。
• 空间复杂度： ，只使用了常数空间。

方法二：异或法

具体做法：
记1到n中所有数字的异或为y=1^2^3……^n；
若序列a中重复的数字为i，记序列a中所有数字的异或为x=1^2^3……^n^i。
因为序列a中有两个一样的数字i，i^i=0，相当于把i抵消了，即序列a所有数字的异或为x=1^2^3……(i-1)^(i+1)……^n
因此要求重复值，只需要将x和y异或，x^y=i;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param a intvector 
     * @return int
     */
    int search(int n, vector<int>& a) {
        // write code here
        int x=0;//计算序列a的异或
        int y=0;//计算1到n的异或
        for(int i=0;i<=n;i++)//
        {
            x=x^a[i];
        }
        for(int i=1;i<=n;i++)
        {
            y=y^i;
        }
        return x^y;//得到重复的数字
    }
};

复杂度分析：

• 时间复杂度： ，只进行了一层遍历。
• 空间复杂度： ，只占用了常数空间。