第六课《失踪宝石调查队——快速判断是否存在》一、国王的宝石失踪了1、一天早晨。程序王国的国王刚刚起床。忽然发现 王者宝石不见了2、国王大喊“不好啦”“我的宝石丢了”3、整个王国立刻行动起来。成立了一支特别小队️ 失踪宝石调查队4、队长小智接到任务“请立刻调查”“看看宝石是否还在仓库里”二、最笨的调查方法1、仓库里有很多箱子红宝石 蓝宝石 绿宝石 黄金 钻石 银币2、现在要找钻石3、最笨的方法看第1个箱子 ↓ 不是 ↓ 看第2个箱子 ↓ 不是 ↓ 看第3个箱子 ↓ 不是一直找到最后。4、如果有100万件宝物怎么办三、智慧大臣的新武器1、智慧大臣说“别傻找了”“我们有哈希表呀”2、于是他拿出unordered_mapstring,int mp;3、记录红宝石 → 1 蓝宝石 → 1 绿宝石 → 1 黄金 → 1 钻石 → 14、这里Key表示宝物名字5、而Value其实不重要。6、重要的是这个宝物在不在四、调查队的问题1、调查队经常问钻石存在吗 黄金存在吗 珍珠存在吗2、这种问题其实都是是否存在3、而不是出现多少次4、所以今天我们要学习快速判断是否存在五、第一个神器count()1、假设仓库unordered_mapstring,int mp; mp[红宝石] 1; mp[蓝宝石] 1; mp[钻石] 1;2、现在调查钻石在吗3、代码cout mp.count(钻石);输出1表示存在六、如果不存在呢1、调查珍珠在吗2、代码cout mp.count(珍珠);输出0表示不存在是不是特别方便七、count() 的含义1、记住mp.count(x)意思x在不在哈希表里2、返回值只有两种1 → 存在 0 → 不存在3、因为unordered_map里面一个 Key 只能有一个。所以不会出现2次 3次 5次八、最经典写法1、调查钻石if(mp.count(钻石)) { cout 找到了; } else { cout 没找到; }2、如果存在找到了否则没找到九、宝石调查系统完整程序#include iostream #include unordered_map using namespace std; int main() { unordered_mapstring,int mp; mp[红宝石] 1; mp[蓝宝石] 1; mp[钻石] 1; string x; cin x; if(mp.count(x)) cout 存在; else cout 不存在; return 0; }输入钻石输出存在输入珍珠输出不存在十、第二个神器find()1、调查队里还有另一位高手。他喜欢使用find()2、例如mp.find(钻石)意思去仓库找钻石十一、find() 返回什么1、如果找到mp.find(钻石)返回宝石位置2、如果找不到返回mp.end()3、所以经典写法if(mp.find(钻石) ! mp.end()) { cout 找到; } else { cout 没找到; }十二、count() 与 find() 对比方法1mp.count(x)适合只关心存在不存在例如宝石在吗方法2mp.find(x)适合还想拿到数据位置例如找到这个人 然后查看信息十三、查重问题来了1、调查队又接到新任务。输入5 2 7 1 3突然又来了一个72、调查队问7是不是已经出现过十四、哈希表秒杀查重建立仓库unordered_mapint,int mp;读到5存进去mp[5] 1;读到2存进去mp[2] 1;读到7存进去mp[7] 1;后来又来了7判断if(mp.count(7))发现存在说明7重复出现了十五、经典题判断是否有重复数字1、输入1 5 2 7 3 5看到1不存在。记录。看到5不存在。记录。看到2不存在。记录。看到7不存在。记录。看到3不存在。记录。2、看到5发现mp.count(5)结果1说明5重复了十六、完整代码#include iostream #include unordered_map using namespace std; int main() { int n; cin n; unordered_mapint,int mp; for(int i0;in;i) { int x; cin x; if(mp.count(x)) { cout 发现重复数字 x endl; } mp[x] 1; } return 0; }十七、时间复杂度为什么快1、假设100万个数字2、普通方法每来一个数字。都去前面找。复杂度O(n²)3、哈希表mp.count(x)平均O(1)总复杂度O(n)快得多十八、比赛中的高频应用1、以后看到下面这些词是否出现过 是否存在 查重 重复数字 重复单词 黑名单 白名单 访问记录2、第一反应unordered_map或者unordered_setunordered_set是unordered_map的阉割版——去掉了 value只留 key专用于去重和存在性判断。十九、小试牛刀1、仓库苹果 香蕉 橘子2、问题1苹果存在吗答案存在3、问题2西瓜存在吗答案不存在4、问题3判断代码if(mp.count(苹果))条件成立吗答案✅ 成立本课总结1、今天我们学会了哈希表第二大应用快速判断是否存在2、核心函数mp.count(x)含义x存在吗返回1 → 存在 0 → 不存在3、另一种写法mp.find(x)4、经典应用✅ 查重✅ 判断存在✅ 黑名单✅ 白名单✅ 访问记录5、经典模板判断是否存在if(mp.count(x)) { cout 存在; } else { cout 不存在; }查重if(mp.count(x)) { cout 重复; } mp[x] 1;6、魔法口诀哈希仓库真奇妙 找东西根本不用找。 count一下马上知 存在不存在全知道。 查重复查名单 哈希表最擅长。 统计次数用 判断存在用count下一课我们将认识哈希表的亲兄弟《魔法通讯录——认识 unordered_set》你会发现有时候我们根本不关心 Value只关心这个东西在不在这时unordered_set就要闪亮登场了
