在长度 2N 的数组中找出重复 N 次的元素 图解题解

长度 2N 的数组里，要揪出哪个数

给一个长度为 2N 的数组 nums，它由 N+1 个各不相同的数拼成：其中 N 个各只出现一次，剩下那一个恰好出现 N 次，要返回的就是这个重复 N 次的数。题面例子 nums=[1,2,3,3] 返回 3（3 出现 2 次，其余各 1 次）；nums=[5,1,5,2,5,3,5,4] 返回 5（5 出现 4 次，别的数各 1 次）。

两两比一遍要 O(n²)，数组一长就吃力

拿每个数往后面挨个比对，看有没有相同的，一撞上就是答案。数组有 2N 个数，两两比较最坏要比约 (2N)²/2 次，是 O(n²)。N 到几万，这个平方级的比对量就顶不住了，得想个只扫一遍的办法。

为什么第一次撞见重复，就能立刻收手

题目埋了一个很硬的保证：全场只有那个重复数会出现第二次，其余每个数都只露一次面。所以一旦发现某个值『之前见过』，它必然就是那个重复 N 次的数——不会是别人，因为别人根本没有第二次。既然如此，就不必真去数它出没出满 N 次，撞上第一次重复的那一刻直接返回即可。

剩下要解决的只是『之前见过吗』怎么查得快。用一个哈希集合 seen：往里丢值、问某个值在不在都快得几乎不花时间，边往右扫边把见过的数丢进去；每到一个数先问集合『你在里面吗』，在就返回它，不在就加进去接着走。

集合边扫边查，一次遍历怎么走完

备一个空集合 seen，指针从最左往右逐个走。对当前值 x：先查 x 是否已在 seen 里，是就直接返回 x（撞上了）；否则把 x 加进 seen，走向下一个。因为重复数出现了 N（≥2）次，扫到它第二次露面时一定会命中，循环保证能返回，不会空手扫到底。

两个题面例子，各在第几个数撞上

先走 [1,2,3,3]。seen 空着，x=1 不在，加进去得 seen={1}；x=2 不在，seen={1,2}；x=3 不在，seen={1,2,3}；最后一个 x=3，一查已经在 seen 里，返回 3。这题的重复数撞在末尾，几乎把数组扫满。

再走 [5,1,5,2,5,3,5,4]。x=5 不在，seen={5}；x=1 不在，seen={5,1}；第三个 x=5，查 seen 发现已经有了，立刻返回 5，后面的 2、5、3、5、4 根本没碰。同一段代码，撞早撞晚全由数据决定。

别真去数满 N 次，也别怕循环提前结束

复杂度上，最坏也只需从头扫到重复数第二次出现，约 N+2 个位置，一遍线性扫下来时间 O(n)；集合里最多攒下那 N 个只出现一次的数，空间 O(n)。

最容易犯嘀咕的是以为非得统计每个数各出现几次、数到 N 才敢下结论——其实只有重复数会有第二次，任何一次重复都来自它，见到即答案。也有人担心循环没扫到底就 return 会漏掉什么，可题目保证这个重复数一定存在，扫到它第二次必然命中，C++、Java 里那种不写终止条件的 for 也会在撞上那刻收手，不会越界。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        s = set()
        for x in nums:
            if x in s:
                return x
            s.add(x)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0;; ++i) {
            if (s.count(nums[i])) {
                return nums[i];
            }
            s.insert(nums[i]);
        }
    }
};

Java

import java.util.*;
class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> s = new HashSet<>(nums.length / 2 + 1);
        for (int i = 0;; ++i) {
            if (!s.add(nums[i])) {
                return nums[i];
            }
        }
    }
}