企业官网建设流程全解析

第八课：《谁偷了国王的金币——查重问题》

一、国王的金币失踪了！

1、一天早晨。

程序王国的国王正在数金币。

2、桌子上放着金币编号：

1001 1002 1003 1004 1005

3、国王每天都会登记新金币。

登记表应该是：

1001 1002 1003 1004 1005

4、可是今天。

管理员小胖发现：

1001 1002 1003 1002 1005

5、咦？

怎么出现了两个：

1002

6、小胖吓坏了：

“国王！”

“金币编号重复了！”

7、国王问：

“能不能快速找出重复金币？”

8、于是。

🕵️‍♂️ 查重特工队出动了！

二、什么叫查重？

查重其实很简单。

1、就是判断：

有没有重复出现的数据

2、例如：

1 5 2 7 3 5

（1）这里：

5

出现两次。

（2）属于：

重复数字

（3）再例如：

Tom Jack Mike Tom

（4）这里：

Tom

重复出现。

3、这就叫：

查重问题

三、最笨的方法

1、假设有：

1 5 2 7 3 5

2、为了检查：

第一个数字

是否重复。

需要和后面所有数字比较。

3、然后：

第二个数字

再比较。

然后：

第三个数字

再比较。

4、画出来：

1 ↔ 5 1 ↔ 2 1 ↔ 7 1 ↔ 3 1 ↔ 5 5 ↔ 2 5 ↔ 7 5 ↔ 3 5 ↔ 5 ...

5、数字越来越多。

比较次数爆炸增长。

如果：

100000个数字

呢？

电脑可能累哭了。

😭

四、哈希表英雄登场

1、智慧大臣笑了：

“为什么要比较那么多次？”

“见过一次就记住它呀！”

2、于是拿出了：

unordered_set<int> s;

3、这个集合就像：

🏢 金币登记中心

4、每看到一个金币编号。

就登记进去。

五、查重的核心思想

1、假设金币依次出现：

1001 1002 1003 1002 1005

2、开始检查。

第一步

看到：

1001

检查：

s.count(1001)

结果：

0

说明：

以前没见过

登记：

s.insert(1001);

登记中心：

1001

第二步

看到：

1002

检查：

s.count(1002)

结果：

0

登记：

s.insert(1002);

登记中心：

1001 1002

第三步

看到：

1003

检查：

不存在

登记。

登记中心：

1001 1002 1003

第四步

看到：

1002

检查：

s.count(1002)

结果：

1

说明：

以前见过！

于是：

🚨🚨🚨

发现重复金币！

六、最重要的查重模板

1、比赛里最常见的代码：

if(s.count(x)) { cout << "发现重复"; } else { s.insert(x); }

2、代码解释：

如果以前见过 说明重复 否则登记

七、完整代码

#include <iostream> #include <unordered_set> using namespace std; int main() { int n; cin >> n; unordered_set<int> s; for(int i=0;i<n;i++) { int x; cin >> x; if(s.count(x)) { cout << "发现重复数字：" << x << endl; } else { s.insert(x); } } return 0; }

输入：

6 1 5 2 7 3 5

输出：

发现重复数字：5

八、升级任务：找到第一个重复数字

1、国王说：

“我只关心最先出现的重复金币。”

2、例如：

1 5 2 7 3 5 2

第一个重复的是：

5

因为：

5

最先第二次出现。

3、代码：

for(int i=0;i<n;i++) { int x; cin >> x; if(s.count(x)) { cout << x; break; } s.insert(x); }

九、升级任务：判断是否有重复

1、有时题目问：

是否存在重复数字？

例如：

1 5 2 7 3

没有重复。

2、代码：

bool repeat = false; for(int i=0;i<n;i++) { int x; cin >> x; if(s.count(x)) { repeat = true; } s.insert(x); }

3、最后：

if(repeat) cout<<"有重复"; else cout<<"无重复";

十、字符串查重

1、不仅数字可以查重。

名字也可以。

2、输入：

Tom Jack Mike Tom Alice

3、代码：

unordered_set<string> s;

4、检查：

if(s.count(name)) { cout<<"重复用户"; }

5、结果：

Tom

被发现重复。

十一、为什么这么快？

1、传统方法：

每个数字。

都和前面比较。

复杂度：

O(n²)

例如：

100000个数字

比较次数：

100000 × 100000

太恐怖了。

2、哈希表：

s.count(x)

平均：

O(1)

总复杂度：

O(n)

速度提升巨大！

十二、竞赛中的经典查重题

1、看到这些词：

重复数字 重复姓名 重复学号 重复单词 是否访问过 是否出现过

2、第一反应：

unordered_set

3、第二反应：

s.count(x)

4、第三反应：

s.insert(x)

十三、经典例题

例题1：统计不同数字

输入：

1 5 2 1 3 5 5 2

放进：

unordered_set<int> s;

最后：

1 2 3 5

答案：

cout << s.size();

输出：

4

例题2：判断是否重复

输入：

7 8 2 5 3

结果：

没有重复

输入：

7 8 2 5 7

结果：

有重复

十四、小试牛刀

输入：

3 1 4 1 5

过程：

看到：

3

登记。

看到：

1

登记。

看到：

4

登记。

看到：

1

发现：

s.count(1)

结果：

1

所以：

🚨

第一个重复数字是：

1

本课总结

1、今天我们学会了哈希表最经典的实战：

查重问题

2、核心容器：

unordered_set<int> s;

3、核心操作：

（1）判断是否见过：

s.count(x)

（2）登记：

s.insert(x);

（3）万能模板：

if(s.count(x)) { // 重复 } else { s.insert(x); }

（4）时间复杂度：

O(n)

必背口诀

查重复，别硬找， 哈希集合效率高。 先检查，再登记， 重复数字跑不掉。 count负责来侦查， insert负责来记牢。 见过一次就记住， 查重问题全解决！

下一课预告

下一课我们将进入哈希表著名的竞赛应用之一：

《神秘数字配对——Two Sum问题》

你将学会一种让无数算法高手着迷的技巧：

target - x

配合：

unordered_map

在一次遍历中找到答案！

很多同学学完这一课后，能真正体会到：

原来哈希表不仅能统计和查重，

还能把看似复杂的问题瞬间变简单！ 🚀