登录四种方法：哈希集合/摩尔投票/邻近元素/随机（Python/Java/C++/Go）
方法一：哈希集合（暴力）
遍历 $\textit{nums}$，同时用一个哈希集合记录遍历过的数。
如果遍历到相同数字（哈希集合中有），由于题目保证只有一个数字是重复的，返回这个数。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
seen = set()
for x in nums:
if x in seen:
return x
seen.add(x)
class Solution {
public int repeatedNTimes(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) { // x 在 seen 中
return x;
}
}
return -1; // 代码不会执行到这里
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) {
if (!seen.insert(x).second) { // x 在 seen 中
return x;
}
}
return -1; // 代码不会执行到这里
}
};
func repeatedNTimes(nums []int) int {
seen := map[int]struct{}{}
for _, x := range nums {
if _, ok := seen[x]; ok {
return x
}
seen[x] = struct{}{}
}
panic(-1)
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
如何做到 $\mathcal{O}(1)$ 空间？下面再介绍三种方法。
方法二：摩尔投票
为了让出现 $n$ 次的那个数变成绝对众数，我们可以分类讨论：
- 如果 $\textit{nums}[0]$ 在下标 $[1,n-1]$ 中出现过，那么返回 $\textit{nums}[0]$。
- 否则，去掉 $\textit{nums}[0]$，剩下 $2n-1$ 个数，出现次数为 $n$ 的那个数变成绝对众数，可以用 169 题的算法解决。
这两件事情可以在同一个循环中完成。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
ans = hp = 0
for x in nums[1:]: # 也可以写 for i in range(1, len(nums)) 避免切片
if x == nums[0]:
return x
if hp == 0: # x 是初始擂主，生命值为 1
ans, hp = x, 1
else: # 比武，同门加血，否则扣血
hp += 1 if x == ans else -1
return ans
class Solution {
public int repeatedNTimes(int[] nums) {
int ans = 0;
int hp = 0;
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x == nums[0]) {
return x;
}
if (hp == 0) { // x 是初始擂主，生命值为 1
ans = x;
hp = 1;
} else { // 比武，同门加血，否则扣血
hp += x == ans ? 1 : -1;
}
}
return ans;
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int ans = 0, hp = 0;
for (int i = 1; i < nums.size(); i++) {
int x = nums[i];
if (x == nums[0]) {
return x;
}
if (hp == 0) { // x 是初始擂主，生命值为 1
ans = x;
hp = 1;
} else { // 比武，同门加血，否则扣血
hp += x == ans ? 1 : -1;
}
}
return ans;
}
};
func repeatedNTimes(nums []int) (ans int) {
hp := 0
for _, x := range nums[1:] {
if x == nums[0] {
return x
}
if hp == 0 { // x 是初始擂主，生命值为 1
ans, hp = x, 1
} else if x == ans { // 比武，同门加血，否则扣血
hp++
} else {
hp--
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。
方法三：检查邻近元素
设出现次数为 $n$ 的那个数为 $x$。
如果相邻两个 $x$ 之间都至少有一个数，那么 $\textit{nums}$ 至少要有 $2n-1$ 个数，这是合法的。
如果相邻两个 $x$ 之间都至少有两个数，那么 $\textit{nums}$ 至少要有 $3n-2$ 个数。
- 如果 $n=2$，这是合法的，例如 $[3,1,2,3]$。
- 如果 $n\ge 3$，那么 $3n-2 > 2n$，不合法。这意味着，当 $n\ge 3$ 时，一定存在 $\textit{nums}[i] = \textit{nums}[i-1]$ 或者 $\textit{nums}[i] = \textit{nums}[i-2]$。
为了兼容 $n=2$ 的情况，我们可以判断 $\textit{nums}[i]$ 是否与下标 $[i-3, i-1]$ 中的元素相等。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
x = nums[i]
if x == nums[i - 1] or \
i > 1 and x == nums[i - 2] or \
i > 2 and x == nums[i - 3]:
return x
class Solution {
public int repeatedNTimes(int[] nums) {
for (int i = 1; ; i++) {
int x = nums[i];
if (x == nums[i - 1] ||
i > 1 && x == nums[i - 2] ||
i > 2 && x == nums[i - 3]) {
return x;
}
}
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
for (int i = 1; ; i++) {
int x = nums[i];
if (x == nums[i - 1] ||
i > 1 && x == nums[i - 2] ||
i > 2 && x == nums[i - 3]) {
return x;
}
}
}
};
func repeatedNTimes(nums []int) int {
for i := 1; ; i++ {
x := nums[i]
if x == nums[i-1] ||
i > 1 && x == nums[i-2] ||
i > 2 && x == nums[i-3] {
return x
}
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。
方法四：随机
在 $\textit{nums}$ 中随机选择两个下标不同的元素，如果两数相等，即找到了重复元素。
首先，在 $[0,n-1]$ 中随机一个数，作为下标 $i$。
然后，我们要在 $[0,i-1]\cup [i+1,n-1]$ 中随机另一个下标 $j$。
但是，标准库只支持在一个连续范围中随机元素，如何在一个间断的区间中随机元素呢？
考虑映射，把 $[0,n-2]$ 映射到 $[0,i-1]\cup [i+1,n-1]$ 中：
$$
f(x) =
\begin{cases}
x, & 0\le x \le i-1 \
x+1, & i\le x \le n-2 \
\end{cases}
$$
具体地，在 $[0,n-2]$ 中随机一个数 $x$：
- 如果 $x < i$，那么把 $x$ 作为下标 $j$。
- 如果 $x \ge i$，那么把 $x+1$ 作为下标 $j$。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
n = len(nums)
while True:
# 在 [0, n-1] 中随机生成两个不同下标
i = randrange(n)
j = randrange(n - 1)
if j >= i:
j += 1
if nums[i] == nums[j]:
return nums[i]
class Solution {
private static final Random rand = new Random();
public int repeatedNTimes(int[] nums) {
int n = nums.length;
while (true) {
// 在 [0, n-1] 中随机生成两个不同下标
int i = rand.nextInt(n);
int j = rand.nextInt(n - 1);
if (j >= i) {
j++;
}
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int n = nums.size();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while (true) {
// 在 [0, n-1] 中随机生成两个不同下标
int i = uniform_int_distribution<>(0, n - 1)(rng);
int j = uniform_int_distribution<>(0, n - 2)(rng);
if (j >= i) {
j++;
}
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
};
func repeatedNTimes(nums []int) int {
n := len(nums)
for {
// 在 [0, n-1] 中随机生成两个不同下标
i := rand.Intn(n)
j := rand.Intn(n - 1)
if j >= i {
j++
}
if nums[i] == nums[j] {
return nums[i]
}
}
}
复杂度分析
- 时间复杂度：期望 $\mathcal{O}(1)$。在 $\textit{nums}$ 中随机选择两个下标不同的元素，两数相等的概率为 $\dfrac{n}{2n}\times \dfrac{n-1}{2n-1}$，当 $n=2$ 时概率为 $p=\dfrac{1}{6}$，当 $n$ 增大时概率 $p\to\dfrac{1}{4}$，期望循环次数 $\dfrac{1}{p} \le 6 = \mathcal{O}(1)$。
- 空间复杂度：$\mathcal{O}(1)$。
专题训练
见下面数学题单的「§6.2 随机化技巧」。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
,
,
,
>
而这一个不是：
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
{:width=600px}
{:width=600px}
{:width=600px}
{:width=600px}
