在长度 2N 的数组中找出重复 N 次的元素 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,3]
- 输出
- 3 （3 出现 2 次,其余各 1 次）
- 输入
- nums=[5,1,5,2,5,3,5,4]
- 输出
- 5 （5 出现 4 次）
先想最直接的笨办法
开局,准备一个空集合 seen,用来记录见过的数。指针从最左边开始,一个一个往右扫。（动画第 4 步）
最优解：一步一步想明白
- 3记住这套「没见过就放进集合,见过就是答案」,下面每一帧都在套它。
- 4开局,准备一个空集合 seen,用来记录见过的数。指针从最左边开始,一个一个往右扫。
- 5走到第 0 个,值 3。先去集合 seen 里查一查,之前见过 3 吗？
- 6集合里没有 3,这是第一次见到它。
- 7把 3 记进集合,继续往后走。
- 8走到第 1 个,值 1。先去集合 seen 里查一查,之前见过 1 吗？
- 9集合里没有 1,这是第一次见到它。
- 10把 1 记进集合,继续往后走。
- 11走到第 2 个,值 2。先去集合 seen 里查一查,之前见过 2 吗？
- 12集合里没有 2,这是第一次见到它。
- 13把 2 记进集合,继续往后走。
- 14走到第 3 个,值 4。先去集合 seen 里查一查,之前见过 4 吗？
- 15集合里没有 4,这是第一次见到它。
- 16把 4 记进集合,继续往后走。
- 17走到第 4 个,值 6。先去集合 seen 里查一查,之前见过 6 吗？
- 18集合里没有 6,这是第一次见到它。
- 19把 6 记进集合,继续往后走。
- 20走到第 5 个,值 8。先去集合 seen 里查一查,之前见过 8 吗？
- 21集合里没有 8,这是第一次见到它。
- 22把 8 记进集合,继续往后走。
- 23走到第 6 个,值 3。先去集合 seen 里查一查,之前见过 3 吗？
- 24集合里已经有 3 了！这说明 3 出现了第二次,正是那个重复 N 次的数。扫描到此结束,答案就是 3。
- 25回头数一数,3（绿色）一共出现了 5 次,正好是题目说的那个重复 N 次的数。哈希集合让我们在第一次撞上时就锁定了它,根本不用数到底。
⚠️ 容易写错的地方
✗ 错：以为要统计每个数出现几次、数到 N 才确定
✓ 对：第一次撞上就是答案,立刻返回
只有重复的数会出现第二次,任何一次重复都来自它,不必数满 N 次
✗ 错：担心循环没扫完就结束、会不会漏
✓ 对：题目保证一定存在这个重复数
C++、Java 的无限 for 一定会在撞上那一刻 return,不会越界
✗ 错：把 Java 的 add 返回值理解反
✓ 对：add 返回 true=新加入成功（没见过）,false=已存在（撞上）
理解反会把第一次见到的数当成答案
完整代码（Python / C++ / Java）
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];
}
}
}
}复杂度
时间
O(n)
最坏约扫到第 N+2 个元素(数组共 2N 个)就撞上
空间
O(n)
集合最多存下约 N 个不同的数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 在长度 2N 的数组中找出重复 N 次的元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用额外集合,有没有 O(1) 空间的解法？+
有。可以证明:重复数的若干次出现中,必然存在某两次的下标距离不超过 3(注意是"存在",并非任意两次都这么近)。所以枚举每个 i,只要把 nums[i] 和后面三个位置 nums[i+1]、nums[i+2]、nums[i+3] 比一比,一旦相等就是答案,完全不用集合,空间 O(1)。不过哈希集合最直观最稳,面试里先写它最稳妥。
为什么一定存在两次出现的间隔不超过 3？+
反证:若重复数所有相邻两次出现的间隔都 ≥4,那么 N 次出现至少要占 4(N−1)+1 个位置;当 N≥2 时这已超过 2N,数组根本塞不下,矛盾。所以必然存在相邻的某两次出现下标距离 ≤3,只需检查距离 1 到 3 的相等对。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 在长度 2N 的数组中找出重复 N 次的元素 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。