第 17 章 从存到算——数组的统计与变换
🏗️ 前情回顾：上一章你学会了用数组把全班 50 个成绩整整齐齐装进一排柜子里——
int scores[50]，再也不用写 50 个变量名了。但柜子装满了，然后呢？老师走过来："平均分多少？最高分是谁？90 分以上有几个？把成绩从小到大排好。"——光有柜子不够，你得会"盘"这些数据。💡 本章要解决的问题：数组存下来了——怎么统计、怎么比较、怎么排序、怎么插入删除？ 这一章，我们解锁数组的"组合技"——遍历不是目的，遍历只是手段；同一组数据换一种遍历方式，就能回答完全不同的问题。
🎯 本章目标
学完这一章，你能：
- 用数组求一组数的和、平均值、最大值和最小值
- 用"桶计数"的思想统计每个数出现了几次
- 在数组中插入、删除、移动元素
- 反转数组、给数组去重
- 认识到同一个数组可以有多种玩法——关键在于"怎么遍历"
📖 故事引入
班长唱票
期末到了，班长小李手里有全班 40 个人的数学成绩单。老师问他三个问题：
- "平均分是多少？"
- "最高分和最低分是谁？"
- "有多少人考了 90 分以上？"
小李没手忙脚乱。他把所有成绩抄在一张纸上，开始唱票——这是他从班级投票里学来的方法。
第一遍唱票——求和、平均：他拿手指从第一个成绩划到最后一个，嘴里念着"85、加 92、加 78……"，最后除以 40，平均分出炉。
第二遍唱票——找最值：他又从头扫一遍，这次不看总分，而是盯"最大的那个"。"85？先记着。92？更大，换掉。78？不如 92，跳过……"扫完，最高分出炉。
第三遍唱票——数人头：再扫一遍，每看到一个 ≥90 的就在纸上画一笔"正"字。三遍扫完，人数也出来了。
三次唱票，都是"从头到尾过一遍"，但每次脑子里的问题不同，结果就不同。这，就是数组统计的核心秘密——遍历是同一把刀，切不同的菜靠的是不同的刀法。
🧱 知识讲解
17.1 求和、均值、最值
这三个操作是数组统计的"老三样"，它们有一个共同特征：初始化一个变量，然后遍历数组，逐个更新这个变量。
求和：
int a[5] = {89, 92, 78, 95, 88};
int sum = 0; // 累加器，从 0 开始
for (int i = 0; i < 5; i++) {
sum = sum + a[i]; // 或者 sum += a[i];
}
cout << "总分：" << sum << endl; // 442
cout << "平均：" << sum / 5.0 << endl; // 88.4求最大值：
int maxVal = a[0]; // 先假设第一个是最大的
for (int i = 1; i < 5; i++) { // 从第二个开始比
if (a[i] > maxVal) {
maxVal = a[i]; // 谁大就替换
}
}
cout << "最高分：" << maxVal << endl; // 95求最小值：把 > 改成 < 就行。
❌ 常见踩坑——最大值初始值设错：
cppint maxVal = 0; // ❌ 如果数组里全是负数，0 就"假冠军"了 int a[5] = {-10, -5, -20, -8, -15}; for (int i = 0; i < 5; i++) { if (a[i] > maxVal) maxVal = a[i]; } cout << maxVal << endl; // 输出 0，但正确答案是 -5！✅ 正确：初始值设为
a[0]——拿数组第一个元素当"暂时的冠军"：cppint maxVal = a[0]; // ✅ 用数组自己的元素做起点
17.2 计数统计——桶思想
"有多少人考了 90 分以上？"这个问题本质是计数：设定一个计数器，遍历数组，每遇到一个符合条件的就加一。
int a[8] = {85, 92, 78, 95, 88, 90, 73, 91};
int cnt = 0; // 计数器
for (int i = 0; i < 8; i++) {
if (a[i] >= 90) {
cnt++;
}
}
cout << "90分以上人数：" << cnt << endl; // 4更进一步的"桶计数"：如果想知道"每个分数各有几个人"呢？这时可以开一个计数数组——数组的下标代表"分数"，数组的值代表"人数"。
int scores[10] = {85, 92, 78, 95, 88, 90, 73, 91, 88, 79};
int bucket[101] = {0}; // 成绩 0~100，共 101 个桶
for (int i = 0; i < 10; i++) {
int s = scores[i]; // 取出第 i 个人的成绩
bucket[s]++; // 在对应的桶里 +1
}
cout << "考 88 分的有 " << bucket[88] << " 人" << endl; // 2
cout << "考 95 分的有 " << bucket[95] << " 人" << endl; // 1这就是桶排序的核心思想——用数组下标天然有序的特性来做统计。后面你会学到完整的桶排序，现在先感受感受。
❌ 常见踩坑——计数数组没初始化：
cppint bucket[101]; // ❌ 没初始化！ bucket[s]++; // 垃圾值 + 1 = 还是垃圾✅ 正确：
cppint bucket[101] = {0}; // ✅ 全部初始化为 0
17.3 数组元素的插入
假设你有一个数组 {10, 20, 30, 40, 50}，想在 20 和 30 之间插入一个 25。怎么做？
数组里没有"缝隙"，你得先把后面的元素整体往后挪一格，腾出空位，再把新元素放进去。
int a[10] = {10, 20, 30, 40, 50}; // 容量 10，目前用了 5 个
int n = 5; // 当前元素个数
// 在位置 2（下标为 2，即 30 的位置）插入 25
int pos = 2;
int val = 25;
// 第一步：从后往前，把 pos 及之后的元素整体后移
for (int i = n; i > pos; i--) {
a[i] = a[i - 1];
}
// 第二步：放入新元素
a[pos] = val;
n++; // 元素个数 +1
// 输出：10 20 25 30 40 50
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}🔑 关键细节：移动要从后往前（
i从n递减到pos+1），如果从前往后移，后面的值还没腾地方就被覆盖了。
❌ 常见踩坑——从前往后移：
cpp// 想在下标 2 处插入 25 for (int i = pos; i < n; i++) { a[i + 1] = a[i]; // ❌ 30 把 40 盖了，40 把 50 盖了 } // 最后整段都是 30✅ 正确——从后往前移：
cppfor (int i = n; i > pos; i--) { a[i] = a[i - 1]; // ✅ 50 先挪到空位 5，40 再挪到空位 4…… }🧠 记忆技巧：排队插队，后面的人先退，才不会踩到前面人的脚。
17.4 数组元素的删除
删除则反过来——把后面的元素整体往前挪一格，盖住要删的那个。
int a[10] = {10, 20, 30, 40, 50};
int n = 5;
// 删除位置 2（即 30）
int pos = 2;
// 从 pos+1 开始，每个元素往前移一位
for (int i = pos; i < n - 1; i++) {
a[i] = a[i + 1];
}
n--; // 元素个数 -1
// 输出：10 20 40 50
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}17.5 数组反转
把 {1, 2, 3, 4, 5} 变成 {5, 4, 3, 2, 1}。
聪明的方法：首尾交换。让第 0 个和第 n-1 个交换，第 1 个和第 n-2 个交换……一直到中间碰头。
int a[5] = {1, 2, 3, 4, 5};
int n = 5;
for (int i = 0; i < n / 2; i++) { // 只需要 n/2 轮
int temp = a[i]; // 经典的三步交换
a[i] = a[n - 1 - i];
a[n - 1 - i] = temp;
}
// 输出：5 4 3 2 1
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}💡
n / 2是关键——如果遍历到n，会把已经换好的又换回去，等于白干。
❌ 常见踩坑——循环到 n：
cppfor (int i = 0; i < n; i++) { // ❌ i 走到 4 时，把换好的又换了回去 swap(a[i], a[n - 1 - i]); } // 结果：1 2 3 4 5（白干！）✅ 正确：
cppfor (int i = 0; i < n / 2; i++) { // ✅ 走到中间就停 swap(a[i], a[n - 1 - i]); }
17.6 数组去重
"去重"就是去掉重复的元素，每个值只保留第一次出现的。
思路：用一个新数组存"只出现过一次"的元素。遍历原数组，对每个元素检查它是否已经在新数组里出现过——没出现过就加进去。
int a[8] = {3, 1, 4, 1, 5, 9, 3, 4};
int n = 8;
int b[8]; // 存去重后的结果
int m = 0; // b 的元素个数
for (int i = 0; i < n; i++) {
bool found = false;
for (int j = 0; j < m; j++) { // 在 b 里找 a[i]
if (b[j] == a[i]) {
found = true;
break;
}
}
if (!found) {
b[m] = a[i]; // 没找到就加进去
m++;
}
}
// 输出去重结果：3 1 4 5 9
for (int i = 0; i < m; i++) {
cout << b[i] << " ";
}🧠 这个去重方法叫"双重循环法"，简单直观但效率不高。学到后面你还会遇到更高效的去重方式（比如先排序再去重）。现在先从最朴素的方法开始，建立直觉。
✋ 动手试试
试试 1：定义一个 int 数组 {65, 34, 87, 23, 98, 56, 72, 41}，分别求最大值、最小值、平均值。平均保留 2 位小数。
试试 2：模拟一个班级的投票——数组里存 20 个数字（1~5），每个数字代表投给一个候选人。用桶计数统计每个人得了多少票，找出票数最高的候选人。
试试 3：有一个已排序（从小到大）的数组，用户输入一个新数字，把它插入到合适的位置，保持数组仍然有序。提示：先找到插入位置，再后移所有元素。
🦶 你踩过这些坑吗？
- [ ] 坑 1：遍历时循环条件写
<=——越界访问arr[n] - [ ] 坑 2：求最大值把初始值设成 0——遇到全负数数组就翻车
- [ ] 坑 3：插入元素时从前往后移——后面的值被覆盖，全变成同一个数
- [ ] 坑 4：反转数组时循环到 n——把换好的又换回去，白干
- [ ] 坑 5：计数数组没初始化——读到的都是垃圾值
- [ ] 坑 6：插入/删除后忘记更新元素个数
n——导致逻辑混乱
📝 练习
基础题
1. 选择题
（1）求数组最大值时，初始值最好设为：
A. 0 B. a[0] C. 100 D. -1
（2）数组反转时，循环应该进行多少次？
A. n 次 B. n/2 次 C. n-1 次 D. 随便
（3）删除数组某个元素后，元素个数 n 应该：
A. 不变 B. n++ C. n-- D. n = 0
2. 填空题
（1）累加求和的计数器通常初始化为 ____。
（2）在位置 pos 插入元素时，需要把从 ____ 到 ____ 的元素整体后移。
（3）去重时需要判断一个元素是否 ____ 出现过。
（4）桶计数的核心思路是用数组的 ____ 代表要统计的"类别"，用数组的 ____ 代表"数量"。
提高题
3. 编程题 — 成绩分析
输入 n 个学生的成绩（0~100），输出：平均分、最高分、最低分、及格人数（≥60）、优秀人数（≥90）。
4. 编程题 — 数组移位
有一个数组，把所有元素循环右移 k 位（k 由用户输入）。比如 {1,2,3,4,5} 右移 2 位变成 {4,5,1,2,3}。（提示：可以借助"反转三次"的技巧：整体反转 → 反转前 k 个 → 反转后 n-k 个。）
5. 编程题 — 有序插入
用户先输入 n 个已经从小到大排好序的整数存入数组，再输入一个新整数 x。把 x 插入到数组中合适的位置，保持数组仍然有序。输出插入后的数组。（提示：先找到 x 应该插入的位置，然后把后面的元素整体后移。）
挑战题
6. 编程题 — 约瑟夫问题简化版
n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出局。下一个人继续从 1 报数。输出出局的顺序。
示例：n=5, m=3 → 出局顺序：3, 1, 5, 2, 4
（提示：用一个 bool 数组标记"是否已出局"，用循环模拟绕圈。）
7. 编程题 — 找众数
输入 n 个整数，找出其中出现次数最多的那个数（众数）。如果有多个数出现次数并列最多，输出最小的那个。例如输入 1 3 2 3 1 3，输出 3（出现了 3 次）。
🧠 本章小结
统计三件套：
求和 sum → 遍历累加
最值 max → 遍历比较（初值设 a[0]！）
计数 cnt → 遍历判条件
桶计数：bucket[ 值 ]++ → 数组下标天然有序
插入：从后往前移 → 腾空位 → 放入
删除：从前往后移 → 覆盖 → n--
反转：首尾交换 → n/2 轮
去重：遍历原数组 → 检查是否出现过 → 加入新数组📝 配套练习
共8题。桶计数是本章核心——J0071/J0074/J0077三题从简单计数到逐位统计到频次分布。。★核心（课堂必做） ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | J0071 | https://hydro.ac/d/srqc/p/J0071 | 桶计数、cnt[]作计数器 |
| ◆ 拓展 | J0074 | https://hydro.ac/d/srqc/p/J0074 | 桶计数、逐位拆解、cnt[10] |
| ◆ 拓展 | J0078 | https://hydro.ac/d/srqc/p/J0078 | 状态数组、!翻转、步进遍历 |
| ◆ 拓展 | J0058 | https://hydro.ac/d/srqc/p/J0058 | 最值、一趟遍历双聚合 |
| ◆ 拓展 | J0076 | https://hydro.ac/d/srqc/p/J0076 | 滑动窗口、前缀和雏形 |
| ◆ 拓展 | J0077 | https://hydro.ac/d/srqc/p/J0077 | 桶计数、频次统计 |
| ◆ 拓展 | luogu-P1554 | https://hydro.ac/p/luogu-P1554 | 桶计数、逐位统计、多区间 |
| ◆ 拓展 | luogu-P5728 | https://hydro.ac/d/srqc/p/J0107 | 嵌套for、两两比较、分数差 |
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 7 道◆拓展题，覆盖不同变式和细节。
配套练习
共8题。桶计数是本章核心——J0071/J0074/J0077三题从简单计数到逐位统计到频次分布。★核心（课堂必做） · ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | J0071 | https://hydro.ac/d/srqc/p/J0071 | 桶计数、cnt[]作计数器 |
| ◆ 拓展 | J0074 | https://hydro.ac/d/srqc/p/J0074 | 桶计数、逐位拆解、cnt[10] |
| ◆ 拓展 | J0078 | https://hydro.ac/d/srqc/p/J0078 | 状态数组、!翻转、步进遍历 |
| ◆ 拓展 | J0058 | https://hydro.ac/d/srqc/p/J0058 | 最值、一趟遍历双聚合 |
| ◆ 拓展 | J0076 | https://hydro.ac/d/srqc/p/J0076 | 滑动窗口、前缀和雏形 |
| ◆ 拓展 | J0077 | https://hydro.ac/d/srqc/p/J0077 | 桶计数、频次统计 |
| ◆ 拓展 | luogu-P1554 | https://hydro.ac/p/luogu-P1554 | 桶计数、逐位统计、多区间 |
| ◆ 拓展 | luogu-P5728 | https://hydro.ac/d/srqc/p/J0107 | 嵌套for、两两比较、分数差 |
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 7 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我能用循环遍历数组，求出一组数的和、平均值、最大/最小值
- [ ] 我会正确设置最大/最小值的初始值（
a[0]，不是 0） - [ ] 我能用桶数组做计数统计，知道必须初始化为
{0} - [ ] 我能在数组中正确插入和删除元素（知道为什么移动方向很重要）
- [ ] 我能在 O(n) 时间内反转一个数组（循环次数是 n/2）
- [ ] 我理解"去重"的思路，能用双重循环实现
- [ ] 我知道插入/删除后要更新元素个数 n
🚀 下章预告
一维数组把全班 50 个人的数学成绩存好了，你也能统计、排序、找最值了。但班主任又来了——"这是全班三门课的成绩单：数学、语文、英语。"你低头一看，这张表有行有列：每行是一个学生，每列是一门科目。一维数组是一条线，装不下带行和列的表格。
下一章，我们给数组加上第二个维度——二维数组，让你像操作 Excel 表格一样，用 a[行][列] 搞定一切矩阵问题！