企业官网建设流程全解析

第五课：《人数统计中心——统计出现次数》

一、统计中心来了一个大任务

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秒钟内判断一个东西是否出现过。

这也是哈希表在比赛中第二重要的应用——查重与快速查找！🚀