GESP7级C++考试语法知识（四、哈希表（5、统计出现次数）
第五课：《人数统计中心——统计出现次数》
一、统计中心来了一个大任务
1、在程序王国里，有一座神秘建筑：
🏢 人数统计中心
这里每天都在统计各种数据。
2、有一天，国王拿来一张名单：
小狗 小猫 小狗 小兔 小狗 小猫3、然后问：
小狗出现了几次？
小猫出现了几次？
小兔出现了几次？
统计员们顿时忙成一团。
二、最笨的方法
1、统计员小胖说：
“简单！”
2、统计小狗：
小狗 ↑ 1 小猫 小狗 ↑ 2 小兔 小狗 ↑ 3 小猫得到：
小狗：3次3、然后统计小猫。
又重新数一遍。
4、然后统计小兔。
再重新数一遍。
5、国王问：
如果有100万个动物怎么办？
小胖：
😨
三、智慧大臣的办法
1、智慧大臣笑着说：
为什么要反复统计？
我们边看边记不就行了吗？
2、于是他拿出了：
哈希统计表
unordered_map<string,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）系统自动创建：
小狗 → 0（2）然后：
0 + 1（3）得到：
小狗 → 13、第二次执行：
cnt["小狗"]++;（1）变成：
1 + 1（2）得到：
小狗 → 2（3）第三次执行：
小狗 → 3神奇吧！
七、数字统计实例
1、我们看看统计数字。
数组：
1 5 2 1 3 5 5 2统计出现次数。
2、建立哈希表：
unordered_map<int,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_map<int,int> cnt; for(int i=0;i<n;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_map<string,int> cnt;3、统计：
cnt[word]++;4、结果：
apple → 3 banana → 2 orange → 1十二、统计字符
1、字符串：
ABACAAB2、代码：
unordered_map<char,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 2（1）第一步：
建立统计表。
（2）最终：
7 → 3 2 → 2 3 → 1（3）问题：
7出现几次？
答案：
3次（4）问题：
2出现几次？
答案：
2次本课总结
1、今天我们学会了哈希表最经典的应用：
统计出现次数
2、核心容器：
unordered_map<int,int> cnt;3、核心代码：
cnt[x]++;4、含义：
看到一个x 次数加15、统计完成后：
cnt[x]表示：
x出现的次数6、经典模板
unordered_map<int,int> cnt; for(int i=0;i<n;i++) { int x; cin >> x; cnt[x]++; }7、魔法口诀
统计问题不用慌， 哈希表来帮你忙。 看到数字记一次， cnt[x]马上加一。 读完数据全知道， 谁多谁少全记牢。 频率统计第一招： cnt[x]++下一课我们将进入：
《失踪宝石调查队——快速判断是否存在》
你将学会：
mp.count(x)和
mp.find(x)如何在1秒钟内判断一个东西是否出现过。
这也是哈希表在比赛中第二重要的应用——查重与快速查找！🚀