【牛客编程巅峰赛S1第3场】找卧底

题目

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

解题思路

解法一先排序，再找重复值
排序可以直接使用 sort() 函数，其时间复杂度为 $O(n \lg n)$ ，接着遍历数组，如果相邻两个数相等，返回重复值。
因此，时间复杂度为 $O(n \lg n)$ ，空间复杂度为 $O(1)$ ，不符合题意。
解法二使用集合存储已遍历过的数值
遍历数组，使用 set 数据结构来保存已遍历过的值，如果当前的值已存在 set 中，表示该值重复。
因此，时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ ，不符合题意。
解法三 位运算（使用这个解法）
求出 1 到 n 的异或值 y，即 y = 1 ^ 2 ^ 3 ... ^ n。
遍历数组，求出它们总的异或值 x，因为有一个重复值 m，有 m ^ m = 0。
所以，遍历数组求出的异或值 x 相当于去掉重复值后的 y，即 x = 1 ^ 2 ^ ... ^ (m-1) ^ (m+1) ^ ... ^ n。
所以，x ^ m = y，所以 m = x ^ y。
时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ ，符合题意。

C++代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int search(int n, vector<int>& a) {
        // write code here
        int x = a[0];
        int y = 0;
        for(int i=1; i<=n; ++i){
            x ^= a[i];
            y ^= i;
        }
        return (x^y);
    }
};