第五课《人数统计中心——统计出现次数》一、统计中心来了一个大任务1、在程序王国里有一座神秘建筑 人数统计中心这里每天都在统计各种数据。2、有一天国王拿来一张名单小狗 小猫 小狗 小兔 小狗 小猫3、然后问小狗出现了几次小猫出现了几次小兔出现了几次统计员们顿时忙成一团。二、最笨的方法1、统计员小胖说“简单”2、统计小狗小狗 ↑ 1 小猫 小狗 ↑ 2 小兔 小狗 ↑ 3 小猫得到小狗3次3、然后统计小猫。又重新数一遍。4、然后统计小兔。再重新数一遍。5、国王问如果有100万个动物怎么办小胖三、智慧大臣的办法1、智慧大臣笑着说为什么要反复统计我们边看边记不就行了吗2、于是他拿出了哈希统计表unordered_mapstring,int cnt;3、这里Key → 动物名字 Value → 出现次数4、例如小狗 → 3 小猫 → 2 小兔 → 1四、统计过程揭秘1、名单小狗 小猫 小狗 小兔 小狗 小猫2、开始统计。第一位小狗看到小狗统计表空于是记录小狗 → 1统计表小狗1第二位小猫看到小猫统计表小狗1增加小猫1变成小狗1 小猫1第三位小狗看到小狗发现已经存在。于是1 1变成小狗2 小猫1第四位小兔变成小狗2 小猫1 小兔1第五位小狗变成小狗3 小猫1 小兔1第六位小猫变成小狗3 小猫2 小兔1最终答案小狗3 小猫2 小兔1五、神奇代码出现了1、智慧大臣只写了一句cnt[x];2、国王惊呆了就这一句3、答案没错就是这一句六、cnt[x] 到底发生了什么1、假设cnt[小狗];2、第一次执行时统计表里没有小狗1系统自动创建小狗 → 02然后0 13得到小狗 → 13、第二次执行cnt[小狗];1变成1 12得到小狗 → 23第三次执行小狗 → 3神奇吧七、数字统计实例1、我们看看统计数字。数组1 5 2 1 3 5 5 2统计出现次数。2、建立哈希表unordered_mapint,int cnt;开始统计。看到1记录1 → 1看到5记录5 → 1看到2记录2 → 1再次看到1更新1 → 23、最终1 → 2 2 → 2 3 → 1 5 → 3八、完整程序#include iostream #include unordered_map using namespace std; int main() { int n; cin n; unordered_mapint,int cnt; for(int i0;in;i) { int x; cin x; cnt[x]; } for(auto p : cnt) { cout p.first 出现 p.second 次 endl; } return 0; }输入8 1 5 2 1 3 5 5 2可能输出可以看到与map,不同在unordered_map中是不自动排字典序的。九、为什么这么快1、以前统计。假设有100000个数字统计数字1扫一遍。统计数字2再扫一遍。统计数字3再扫一遍。总复杂度O(n²)非常慢。2、而哈希表cnt[x];边读边统计。只扫描一次。复杂度O(n)快了非常多十、竞赛中最经典的模板1、以后看到统计出现次数 统计频率 统计人数 统计字符 统计单词脑海里立刻想到unordered_map类型,int cnt;2、然后cnt[x];这是哈希表最重要的用法。没有之一。十一、统计字符串1、例如apple banana apple orange apple banana2、代码unordered_mapstring,int cnt;3、统计cnt[word];4、结果apple → 3 banana → 2 orange → 1十二、统计字符1、字符串ABACAAB2、代码unordered_mapchar,int cnt;3、统计cnt[c];4、结果A → 4 B → 2 C → 1十三、经典例题1、例题谁出现次数最多输入1 5 2 1 3 5 5 22、统计后1 → 2 2 → 2 3 → 1 5 → 33、最多的是5出现3次十四、小试牛刀1、请统计7 7 2 7 3 21第一步建立统计表。2最终7 → 3 2 → 2 3 → 13问题7出现几次答案3次4问题2出现几次答案2次本课总结1、今天我们学会了哈希表最经典的应用统计出现次数2、核心容器unordered_mapint,int cnt;3、核心代码cnt[x];4、含义看到一个x 次数加15、统计完成后cnt[x]表示x出现的次数6、经典模板unordered_mapint,int cnt; for(int i0;in;i) { int x; cin x; cnt[x]; }7、魔法口诀统计问题不用慌 哈希表来帮你忙。 看到数字记一次 cnt[x]马上加一。 读完数据全知道 谁多谁少全记牢。 频率统计第一招 cnt[x]下一课我们将进入《失踪宝石调查队——快速判断是否存在》你将学会mp.count(x)和mp.find(x)如何在1秒钟内判断一个东西是否出现过。这也是哈希表在比赛中第二重要的应用——查重与快速查找
