数组综合应用

官官方信息技术老师·18 页·深入(追求细节与边界)·0 次浏览·38 天前
数组双指针边界条件算法

数组综合应用

看完你能独立分析四个经典题的边界条件与最优解法

按 空格/→ 演示下一步

问一句
1 / 18 页

全部页面点击任意一页,跳回舞台从这页播放

数组双指针边界条件算法

数组综合应用

看完你能独立分析四个经典题的边界条件与最优解法

1第 1 页 · 数组综合应用

问题拆解:成绩统计要算什么

上一页把全班成绩存进了一个数组。数据在手,老师月底要交总评表——光「存起来」不够,得先想清楚要算什么,才能动手写代码。

求和
所有元素累加,得到班级总分
均值
总分除以人数,衡量整体水平
最值
遍历时打擂台,找最高与最低分
分布
按分数段计数,看各档人数
月底报账对应 →成绩统计

流水账求和对应总分,日均开销对应均值,最大一笔对应最值

2第 2 页 · 问题拆解:成绩统计要算什么

成绩统计完整代码

python

用一段真实可运行的 Python,看遍历累加如何算出总分与均值,并理解初值为什么关键。

代码高亮加载中…

累加器 total 初始化为 0,循环中逐个累加,循环外除以个数得均值——三步构成统计的完整骨架。

3第 3 页 · 成绩统计完整代码

最值与分布的遍历细节

把成绩数组的两个经典遍历——打擂台找最值和计数数分布——拆成一步步看清。

1
初始化擂主
max 先放 arr[0],不能放 0:全负数时结果就错了。
2
从第二个比起
i 从 1 开始,arr[0] 已在擂台,自己不用比自己。
3
逐个打擂
arr[i] > max 才更新,用 > 而不是 >=,避免无谓覆盖。
4
建计数桶
先开好 count 数组并清零,每个下标对应一个分数段。
5
按值入桶
遍历成绩,count[score]++,下标即分数本身。
6
扫桶出分布
再遍历 count,桶非零即为该分数出现次数。
4第 4 页 · 最值与分布的遍历细节

自测:成绩统计

点击作答

求全班最高分时,把 max 初值设为 0 再遍历比较,什么情况下会得出错误结论?

5第 5 页 · 自测:成绩统计

去重的难点在哪

上一页成绩统计只需遍历一次,因为不用改动数组。可去重要删元素:删掉一个,后面全得往前挪。难点不在“找到重复”,而在“挪动的同时不把遍历搞乱”。

删后要挪
删除位置 i 的元素后,后面每个元素都要前移一位
指针别乱
删除后不能立刻 i++,否则会跳过刚挪过来的新元素
原地压缩
用写指针只保留不重复元素,一遍扫完,避免每删一个就搬一次
规模收缩
原地压缩后有效长度变小,尾部旧数据视为废弃
整理书架抽走一本对应 →数组删除元素

抽走一本后,右边的书都要往左补位

6第 6 页 · 去重的难点在哪

双下标原地压缩流程

读写双下标一次扫描,把重复字符原地压掉,只留首次出现。

1
建读写指针
读指针从0出发扫描,写指针指向可写入位置,初始都在0
2
读指针扫描
读指针逐个检查字符,判断它是否已写入过
3
查是否新字符
回头扫描前缀找当前字符;找不到说明是首次出现
4
写入并推进
新字符才写入写指针位置,写指针加1,保留首次出现
5
读指针前进
无论是否写入,读指针都加1,继续下一个字符
6
截断输出
扫描结束,前写指针个字符就是去重结果
7第 7 页 · 双下标原地压缩流程

删除重复字符代码

c

用双下标原地压缩删除重复字符,看字符串结尾 '\0' 如何收尾。

代码高亮加载中…

读指针 r 扫描原串,写指针 w 只收首次出现的字符;循环到 '\0' 停止后,必须手动写 s[w]='\0',否则尾部残留旧字符。

8第 8 页 · 删除重复字符代码

手推一遍压缩过程

从左到右看每个箭头:r 走到哪个字符,判断重复后决定写入 w 或跳过。

图解渲染中…
g3:r=2 的 b 与已写入的 b 重复,原地跳过g6:前 w=3 个格子即去重结果,后面丢弃g1:w 指向下一个可写位置,写后 w 加一
9第 9 页 · 手推一遍压缩过程

分类计数的思想

前面统计成绩时,你写了一串 if:90 分加一、80 分加一……分支越写越多。有没有想过,分数本身就指着一行格子?这一页讲一个更聪明的做法。

下标当类别
分数、等级、字符本身就能当数组下标
计数数组
cnt[score]++ 一行完成归类与累加
替代 if 串
几十个分支缩成一句,代码与分支数无关
遍历一次出结果
最后按下标扫一遍计数数组即可
酒店房间号对应 →计数数组下标

客人的房间号对应数据的类别,进门住下对应计数加一

10第 10 页 · 分类计数的思想

统计字符代码

python

一次遍历字符串,用计数数组按类别累加,看看各字符归到哪一桶。

代码高亮加载中…

counts 数组就是四个桶,每个字符判断类别后让对应下标自增,一次遍历完成全部统计。

11第 11 页 · 统计字符代码

自测:统计字符

检验对分类条件与计数初始化的理解

自测:统计字符
检验对分类条件与计数初始化的理解
12第 12 页 · 自测:统计字符

矩阵相乘的规则

前面我们用一维数组统计成绩、去重、计数。现在把一维数组竖起来再排一排,就成了矩阵。两个矩阵能不能相乘、怎么相乘,规则只有一句话:内维相等,行列对应相乘再求和。

内维必须相等
A 的列数要等于 B 的行数,否则乘法无定义
结果尺寸
A 是 m×n、B 是 n×k,结果 C 是 m×k
逐元素计算
C[i][j] 等于 A 第 i 行与 B 第 j 列对应相乘后求和
点菜结账对应 →矩阵相乘

菜单行对应订单列,逐项单价乘数量再求和

C[i][j]=∑k=0n−1A[i][k]⋅B[k][j]C[i][j]=\sum_{k=0}^{n-1} A[i][k]\cdot B[k][j]
13第 13 页 · 矩阵相乘的规则

乘法过程图解

看C行如何与A列逐对相乘再累加:抓住行列相遇点和sum的推进。

图解渲染中…
e1:写入后重置sum为0,进入下一个j
14第 14 页 · 乘法过程图解

三重循环实现

c

用三重 for 循环把矩阵乘法规则翻译成代码,看清三层各管什么。

代码高亮加载中…

i、j 锁定结果 c[i][j] 的位置,k 扫描一行乘一列并累加——三层循环各司其职,次序不能乱。

15第 15 页 · 三重循环实现

易错点辨析

三个坑杀伤力最大:下标反了、内维不等、累加没清零。左右对照一次看懂错在哪、怎么改。

错误写法
  • 写 a[j][i],行列下标搞反
  • 内维不相等也直接相乘
  • sum 在外层循环外只初始化一次
正确写法
  • a[i][j],i 管行、j 管列
  • 先检查 A 列数 == B 行数
  • sum 在最内层循环前清零
正确的理解是:下标含义看语义、乘法先验内维相等、累加变量必须每轮重置,三者缺一不可。
16第 16 页 · 易错点辨析

数组应用总结

  • ✓所有套路起点都是遍历,先想清下标含义再写
  • ✓计数类:一个下标扫,哈希式数组做桶
  • ✓原地压缩:双下标读写分离,空间省一半
  • ✓多层数据叠加:循环层数=问题嵌套深度
  • ✓边界 lastIndex、越界、空数组先想后写
延伸主题:排序算法中的数组应用二维数组与矩阵进阶操作用结构体数组组织复杂数据
17第 17 页 · 数组应用总结

课后思考

三个问题没有标准答案,先自己想十分钟,再对照参考思路。

1成绩统计里最值和分布一次遍历就能同时算出来,为什么循环次数反而更少却更清晰?

参考答案往「减少重复遍历」想:同一趟循环里每个元素顺手做三件事,数据只读一遍。关键是每个 if 各管一件事,逻辑没搅在一起,所以既省了次数又不牺牲可读性。

2如果要把成绩统计改成统计上千门课程的成绩,代码结构该怎么变?

参考答案往「数组套数组」想:一门课是一个数组,多门课就是二维数组。内层循环算单门的和与最值,外层循环遍历课程——和矩阵相乘的双层结构是同一套思路。

3原地压缩去重要求数据有序才高效,如果数据无序还有哪些可行的去重思路?

参考答案可以先用排序再压缩(代价 O(n log n)),也可以用辅助数组或哈希表记录「见过没有」(用空间换时间,一趟搞定)。比较三种方案在时间和空间上的取舍。

18第 18 页 · 课后思考