第五课：《人数统计中心——统计出现次数》
一、统计中心来了一个大任务
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）得到：
小狗 → 1
3、第二次执行：
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 → 2
3、最终：
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
banana
2、代码：
unordered_map<string,int> cnt;
3、统计：
cnt[word]++;
4、结果：
apple → 3
banana → 2
orange → 1
十二、统计字符
1、字符串：
ABACAAB
2、代码：
unordered_map<char,int> cnt;
3、统计：
cnt[c]++;
4、结果：
A → 4
B → 2
C → 1
十三、经典例题
1、例题：谁出现次数最多？
输入：
1 5 2 1 3 5 5 2
2、统计后：
1 → 2
2 → 2
3 → 1
5 → 3
3、最多的是：
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
次数加1
5、统计完成后：
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秒钟内判断一个东西是否出现过。
这也是哈希表在比赛中第二重要的应用——查重与快速查找！🚀
