第八课《谁偷了国王的金币——查重问题》一、国王的金币失踪了1、一天早晨。程序王国的国王正在数金币。2、桌子上放着金币编号1001 1002 1003 1004 10053、国王每天都会登记新金币。登记表应该是1001 1002 1003 1004 10054、可是今天。管理员小胖发现1001 1002 1003 1002 10055、咦怎么出现了两个10026、小胖吓坏了“国王”“金币编号重复了”7、国王问“能不能快速找出重复金币”8、于是。️‍♂️ 查重特工队出动了二、什么叫查重查重其实很简单。1、就是判断有没有重复出现的数据2、例如1 5 2 7 3 51这里5出现两次。2属于重复数字3再例如Tom Jack Mike Tom4这里Tom重复出现。3、这就叫查重问题三、最笨的方法1、假设有1 5 2 7 3 52、为了检查第一个数字是否重复。需要和后面所有数字比较。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_setint s;3、这个集合就像 金币登记中心4、每看到一个金币编号。就登记进去。五、查重的核心思想1、假设金币依次出现1001 1002 1003 1002 10052、开始检查。第一步看到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_setint s; for(int i0;in;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 i0;in;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 i0;in;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 Alice3、代码unordered_setstring 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_set3、第二反应s.count(x)4、第三反应s.insert(x)十三、经典例题例题1统计不同数字输入1 5 2 1 3 5 5 2放进unordered_setint 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_setint 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在一次遍历中找到答案很多同学学完这一课后能真正体会到原来哈希表不仅能统计和查重还能把看似复杂的问题瞬间变简单