961. N-Repeated Element in Size 2N Array

961. 重复 N 次的元素

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

1. 4 <= A.length <= 10000
2. 0 <= A[i] < 10000
3. A.length 为偶数

解法一

//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:int repeatedNTimes(vector<int>& A) {unordered_set<int> us;for(int elem : A) {if(us.count(elem)) return elem;us.insert(elem);}return 0;}
};

解法二

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:int repeatedNTimes(vector<int>& A) {for(int k = 1; k < 4; k++) {int right = A.size() - k;for(int i = 0; i < right; i++) {if(A[i] == A[i + k]) return A[i];}}return 0;}
};

思路：

解法一

使用一个额外的哈希表记录出现过的元素，直到遇到一个出现两次的元素，将其返回。

这个解法利用了隐含条件：除了要求的元素以外其他元素均只出现一次，所以如果遇到重复一次的元素，那它一定是要求的N-Repeated Element。

解法二

为了节省空间，使用三次遍历，分别检查以步长k（1、2、3）为间隔的连续元素是否相同，如果有就将其返回。

这个解法利用了这样一个隐含条件：对于长为n（n > 2且为偶数）的数组，出现次数为n / 2的元素在每相邻四个元素中至少出现2次。

注：如果题上的重复n次条件变为重复n + 1次，这个题目就变成了第169题求众数，使用摩尔投票法可以一次遍历完成求解。