284 lines
7.7 KiB
Markdown
284 lines
7.7 KiB
Markdown
# 第9课：数组计数法
|
||
|
||
## 教学目标
|
||
|
||
- 理解“数值作下标、次数存数组”的计数思想
|
||
- 掌握数组计数的核心写法 `cnt[x]++`
|
||
- 能用计数数组完成频次统计、最高频查找和去重升序输出
|
||
- 知道数组计数法的适用条件和下标范围限制
|
||
|
||
## 核心考点：数值映射为下标的数组计数思想
|
||
|
||
### 考什么
|
||
题目会给出一组范围明确的整数，要求统计频次、找出现次数最多的数、判断某数是否出现，或去重后按序输出。关键是不用两两比较，而是让每个数直接找到自己的计数位置。
|
||
|
||
### 必须理解
|
||
当数值 x 能作为合法下标时，用 `cnt[x]` 表示 x 出现的次数。每读到一次 x，就执行 `cnt[x]++`。统计结束后，遍历计数数组即可获得所有频次；因为下标从小到大遍历，输出天然有序。使用前必须根据数据范围确定数组大小并清零。若存在负数，可在范围较小时整体偏移；若数值范围极大，就不适合直接开计数数组。
|
||
|
||
### 核心写法
|
||
```cpp
|
||
int cnt[101] = {};
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
cnt[x]++;
|
||
}
|
||
for (int value = 0; value <= 100; value++) {
|
||
if (cnt[value] > 0) {
|
||
cout << value << ' ' << cnt[value] << endl;
|
||
}
|
||
}
|
||
```
|
||
这里下标 `value` 代表具体数值，数组元素 `cnt[value]` 代表次数，两者含义不能混淆。
|
||
|
||
### 常见错误
|
||
- 数值范围到100，却只开 `cnt[100]`，无法访问下标100。
|
||
- 计数数组未清零，初始垃圾值会参与累加。
|
||
- 输入可能为负数或超范围，仍直接作为下标导致越界。
|
||
- 输出最高频数字时混淆“数字本身”和“出现次数”。
|
||
|
||
### 判断是否掌握
|
||
能根据数据范围确定计数数组大小，能解释 `cnt[x]++` 的含义，并能通过一次计数、一次遍历完成频次查询、众数或去重输出。
|
||
|
||
---
|
||
|
||
## 课前认识：什么是数组计数法
|
||
|
||
如果输入的数字都在 `0~100` 之间，可以准备一个 `cnt[101]` 数组：
|
||
|
||
- 数字 `x` 出现一次，就执行 `cnt[x]++`
|
||
- `cnt[3]` 表示数字 3 出现了几次
|
||
- `cnt[100]` 表示数字 100 出现了几次
|
||
|
||
例如输入 `3 1 3 2 1 3`，计数后有：
|
||
|
||
| 数字（下标） | 0 | 1 | 2 | 3 |
|
||
|---|---:|---:|---:|---:|
|
||
| 次数（cnt） | 0 | 2 | 1 | 3 |
|
||
|
||
> 数组计数法的核心，就是把数字直接放到对应编号的“小格子”里做记号。
|
||
|
||
---
|
||
|
||
## 题目一：统计数字出现次数
|
||
|
||
### 题目描述
|
||
|
||
输入 n 个 `0~100` 之间的整数，按数字从小到大的顺序，输出每个出现过的数字及其出现次数。
|
||
|
||
### 核心代码（一句话）
|
||
|
||
> 每读到一个数字 `x`，就让对应位置加一：`cnt[x]++`。
|
||
|
||
### 自然语言思路
|
||
|
||
第一步，准备 `cnt[101]`，把每个位置都初始化为 0。
|
||
|
||
第二步，循环读入 n 个数字。读到 `x`，就在编号为 x 的格子里加一次，也就是 `cnt[x]++`。
|
||
|
||
第三步，从 0 遍历到 100。若 `cnt[i] > 0`，说明数字 i 出现过，输出 i 和它的次数。
|
||
|
||
### 伪代码
|
||
|
||
```text
|
||
1. 输入 n
|
||
2. 创建并清零计数数组 cnt[101]
|
||
3. 重复 n 次：
|
||
4. 输入 x
|
||
5. cnt[x] 加 1
|
||
6. 从 i = 0 遍历到 100：
|
||
7. 如果 cnt[i] > 0：
|
||
8. 输出 i 和 cnt[i]
|
||
```
|
||
|
||
### 真实代码
|
||
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
|
||
int cnt[101] = {};
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
cnt[x]++;
|
||
}
|
||
|
||
for (int i = 0; i <= 100; i++) {
|
||
if (cnt[i] > 0) {
|
||
cout << i << ":" << cnt[i] << endl;
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
|
||
- `int cnt[101] = {};` 会把整个数组清零。
|
||
- 数值范围是 `0~100`，所以数组需要 101 个位置。
|
||
- 输出时只输出 `cnt[i] > 0` 的数字。
|
||
- 输入值不能超出数组下标范围，否则会越界。
|
||
|
||
---
|
||
|
||
## 题目二：寻找出现次数最多的数字
|
||
|
||
### 题目描述
|
||
|
||
输入 n 个 `0~100` 之间的整数，输出出现次数最多的数字。如果多个数字出现次数相同，输出其中较小的数字。
|
||
|
||
### 核心代码（一句话）
|
||
|
||
> 先用 `cnt[x]++` 统计次数，再从小到大打擂台；只有次数严格更多时才更换答案。
|
||
|
||
### 自然语言思路
|
||
|
||
第一步，先像题目一一样统计每个数字出现的次数。
|
||
|
||
第二步，假设数字 0 暂时是擂主，用 `bestValue` 保存擂主数字，用 `bestCount` 保存它的出现次数。
|
||
|
||
第三步，从数字 1 遍历到 100。如果 `cnt[i] > bestCount`，说明 i 出现得更多，让 i 成为新擂主。
|
||
|
||
第四步，如果次数相同，不更换擂主。因为我们从小到大遍历，先成为擂主的数字更小，正好满足并列时取较小值。
|
||
|
||
### 伪代码
|
||
|
||
```text
|
||
1. 输入 n，统计 cnt
|
||
2. bestValue = 0
|
||
3. bestCount = cnt[0]
|
||
4. 从 i = 1 遍历到 100：
|
||
5. 如果 cnt[i] > bestCount：
|
||
6. bestValue = i
|
||
7. bestCount = cnt[i]
|
||
8. 输出 bestValue
|
||
```
|
||
|
||
### 真实代码
|
||
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
|
||
int cnt[101] = {};
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
cnt[x]++;
|
||
}
|
||
|
||
int bestValue = 0;
|
||
int bestCount = cnt[0];
|
||
for (int i = 1; i <= 100; i++) {
|
||
if (cnt[i] > bestCount) {
|
||
bestValue = i;
|
||
bestCount = cnt[i];
|
||
}
|
||
}
|
||
|
||
cout << bestValue << endl;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
|
||
- 题目保证 `n >= 1`，因此一定存在答案。
|
||
- 判断条件必须是 `>`，不能写成 `>=`；否则并列时会留下较大的数字。
|
||
- `bestValue` 保存数字，`bestCount` 保存次数，不要混淆。
|
||
- 这道题把第4课的“打擂台”和本课的数组计数结合了起来。
|
||
|
||
---
|
||
|
||
## 题目三：去重后升序输出
|
||
|
||
### 题目描述
|
||
|
||
输入 n 个 `0~100` 之间的整数，去掉重复数字，并按从小到大的顺序输出。
|
||
|
||
### 核心代码（一句话）
|
||
|
||
> 计数后从小到大遍历下标，`cnt[i] > 0` 就输出 i，每个数字只输出一次。
|
||
|
||
### 自然语言思路
|
||
|
||
第一步，用计数数组记录每个数字是否出现过。
|
||
|
||
第二步，从 0 遍历到 100。数组下标本身就是数字，而且遍历顺序天然是从小到大。
|
||
|
||
第三步，只要 `cnt[i] > 0`，就输出一次 i。不管它原来出现两次还是十次，都只输出一次，因此完成去重。
|
||
|
||
### 伪代码
|
||
|
||
```text
|
||
1. 输入 n，统计 cnt
|
||
2. 从 i = 0 遍历到 100：
|
||
3. 如果 cnt[i] > 0：
|
||
4. 输出 i
|
||
```
|
||
|
||
### 真实代码
|
||
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
|
||
int cnt[101] = {};
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
cnt[x]++;
|
||
}
|
||
|
||
bool first = true;
|
||
for (int i = 0; i <= 100; i++) {
|
||
if (cnt[i] > 0) {
|
||
if (!first) cout << ' ';
|
||
cout << i;
|
||
first = false;
|
||
}
|
||
}
|
||
cout << endl;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
|
||
- 遍历计数数组时，下标本身按从小到大变化，因此输出天然有序。
|
||
- 去重只关心“是否出现”，所以判断 `cnt[i] > 0` 即可。
|
||
- `first` 用来控制空格，避免行首或行尾出现多余空格。
|
||
- 如果数字范围非常大，例如到 `10^9`，就不适合直接开这么大的计数数组。
|
||
|
||
---
|
||
|
||
## 本课打油诗
|
||
|
||
> 数值下标来对号，
|
||
> 每次出现次数高。
|
||
> 从小到大逐格找，
|
||
> 统计去重一招好。
|
||
|
||
---
|
||
|
||
## 课后作业
|
||
|
||
1. 输入 n 个 `0~50` 的整数，再输入一个数字 q，输出 q 出现了多少次。
|
||
2. 输入 n 个 `0~100` 的整数，输出出现次数最少且出现过的数字；并列时输出较小者。
|
||
3. 输入 n 个学生的分数（`0~100`），依次输出每个分数段的人数：不及格、60~79、80~89、90~100。
|
||
|
||
> 提示：先判断题目中的数字范围，再决定计数数组要开多大。
|