题目描述

在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。

返回重复了 N 次的那个元素。

样例

输入：[1,2,3,3]
输出：3

输入：[2,1,2,5,3,2]
输出：2

输入：[5,1,5,2,5,3,5,4]
输出：5

限制

• 4 <= A.length <= 10000
• 0 <= A[i] < 10000
• A.length 是偶数

算法

(线性遍历，抽屉原理) $O(n)$

1. 由于题目中说了必定有 N+1 个不同数字，我们考虑将整个数组划分为 $(a_1, a_2), (a_3, a_4), \cdot, (a_{n - 1}, a_n)$。
2. 如果某一组中的 $a_i = a_{i+1}$，则 $a_i$ 就是答案；否则，每一组都必定有一个数字是答案，此时可以判断 $a_1$ 和 $a_2$ 哪个是答案即可。

时间复杂度

• 由于只遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 使用了常数的空间。

C++ 代码

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int n = A.size();
        for (int i = 0; i < n; i += 2)
            if (A[i] == A[i + 1])
                return A[i];

        if (A[0] == A[2] || A[0] == A[3])
            return A[0];

        return A[1];
    }
};