题解 | #找出重复的数#

题意整理：

基本题意

或许是一道经典的面试题。

给出一个长度为 $n+1$ 的整数数列 $a_0,a_1,a_2,...a_n$ ，保证里面 $1,2,3,...,n$ 都出现至少一次，同时有且仅有一个数字出现过两次。

找出这个出现过两次的数字。

数据范围与性质

$1\le n \le 10^5, 1\le a_i \le n$ 。

要求使用时间复杂度为 $O(n)$ ，额外空间（指输入数据的 $\text{vector}$ 以外的空间）为 $O(1)$ 的算法。

解法1：朴素算法（不满足空间限制）

【算法】朴素算法

实现与分析

用一个额外的 $cnt$ 数组统计每个数字出现的次数，如果一个数字的出现次数超过 $1$ ，则它就是答案。

用 $\text{for}$ 循环和数组实现即可。

时空间复杂度 $O(n)$ 。

参考代码

//c++
class Solution {
public:
    int cnt[100001];
    int search(int n, vector<int>& a) {
          memset(cnt,0,sizeof(cnt));//初始化cnt数组为 0
        for(int i=0;i<=n;i++)
            cnt[a[i]]++;//统计每个数字的出现次数
        for(int i=1;i<=n;i++)
            if(cnt[i]>1)
                return i;//找到答案

        return 0;
    }
};

吐槽

牛客并没有限制 $O(n)$ 时间和 $O(1)$ 空间，这个代码在牛客上依然可以 $\text{AC}$ 。

解法2：数字分拣

【算法】小技巧

实现与分析

思考如何利用好输入数列本身的空间。

注意，数据范围都在 $1$ 到 $n$ 以内，如果我们能够把输入数列中的 $i$ 放到 $a[i]$ 位置，那么肯定有一个多出来的数字它没有地方放，只能放在 $a[0]$ 。

那么我们不妨就这么做，目标是把每个数字分拣，让 $a[i]=i$ 。于是我们对 $a[0]$ 进行考虑：

我们就把 $a[0]$ 与 $a[a[0]]$ 交换，换句话说，这可以让数字 $a[0]$ 到达它目标位置。如果发现 $a[0]=a[a[0]]$ 了，说明答案就是 $a[0]$ ，这时结束算法。

我们通过一个例子来演示算法过程：

考虑某个样例的执行过程：

4,[1,3,4,2,1]

$\text{STEP：1}$

图片说明

$\text{STEP：2}$

图片说明

$\text{STEP：3}$

图片说明

$\text{STEP：4}$

图片说明

$\text{STEP：5}$

图片说明

答案为 $1$ 。

参考代码

//c++
class Solution {
public:

    int search(int n, vector<int>& a) {
        for(int i=0;i<=n;i++)
        {
            if(a[0]==a[a[0]]) return a[0];//如果找到重复的数字了，结束算法

            int t=a[a[0]];
            a[a[0]] = a[0];//否则把当前数字交换到其目标位置
            a[0] = t;
        }
        return 0;
    }
};

上面的算法总是能在 $O(n)$ 步结束，因为每次交换两个数字的时候，总能把一个数字放到目标位置去，一旦所有数字都到达目标位置了，算法一定会结束，所以时间复杂 $O(n)$ 。
因为额外的空间仅仅是交换两个数时用到的一个空间，所以额外空间复杂度 $O(1)$ 。

补充解法：运算法

加和运算法：

因为数据保证数字 $1,2,...n$ 各出现一次，然后目标数字额外出现一次，那么显然 $(\sum_{i=1}^{n+1}a_i)-\sum_{i=1}^ni$ 就是答案，即用所有数字和减去 $1+2+..+n$ 的结果就得到了额外出现一次的数字。
代码：

class Solution {
public:

    int search(int n, vector<int>& a) {
          long long sum_a=0,sum=0;
        for(int i=0;i<=n;i++)
            sum_a+=a[i];
        for(int i=1;i<=n;i++)
            sum+=i;
        return sum_a-sum;
    }
};

这样只需要维护 $O(1)$ 的额外空间来进行累加运算，累加过程需要遍历大小为 $O(n)$ 的数组，因此时间复杂度 $O(n)$ ，额外空间复杂度 $O(1)$ 。

异或和运算法：

二进制整数的按位异或运算满足传说中的交换律，并且自身就是自己的逆运算。
令 $\oplus$ 表示按位异或运算。那么可以的得到： $\bigoplus _{i=1}^{n+1} a_i = (\bigoplus _{i=1}^{n} i)\oplus ans$
于是就有 $ans=(\bigoplus _{i=1}^{n+1} a_i)\oplus (\bigoplus _{i=1}^{n} i)$
也就是说，只需要求出 $a_i$ 的异或和，以及 $1\oplus 2\oplus ..\oplus n$ 的异或和，两者相互异或就是答案。
代码：

class Solution {
public:

    int search(int n, vector<int>& a) {
          int sum_a=0,sum=0;
        for(int i=0;i<=n;i++)
            sum_a^=a[i];
        for(int i=1;i<=n;i++)
            sum^=i;
        return sum_a^sum;
    }
};

同样，只需要维护 $O(1)$ 的额外空间来进行累异或运算，需要遍历大小为 $O(n)$ 的数组，因此时间复杂度 $O(n)$ ，额外空间复杂度 $O(1)$ 。