数组综合应用
看完你能独立分析四个经典题的边界条件与最优解法
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
数组综合应用
看完你能独立分析四个经典题的边界条件与最优解法
问题拆解:成绩统计要算什么
上一页把全班成绩存进了一个数组。数据在手,老师月底要交总评表——光「存起来」不够,得先想清楚要算什么,才能动手写代码。
流水账求和对应总分,日均开销对应均值,最大一笔对应最值
成绩统计完整代码
用一段真实可运行的 Python,看遍历累加如何算出总分与均值,并理解初值为什么关键。
累加器 total 初始化为 0,循环中逐个累加,循环外除以个数得均值——三步构成统计的完整骨架。
最值与分布的遍历细节
把成绩数组的两个经典遍历——打擂台找最值和计数数分布——拆成一步步看清。
自测:成绩统计
求全班最高分时,把 max 初值设为 0 再遍历比较,什么情况下会得出错误结论?
去重的难点在哪
上一页成绩统计只需遍历一次,因为不用改动数组。可去重要删元素:删掉一个,后面全得往前挪。难点不在“找到重复”,而在“挪动的同时不把遍历搞乱”。
抽走一本后,右边的书都要往左补位
双下标原地压缩流程
读写双下标一次扫描,把重复字符原地压掉,只留首次出现。
删除重复字符代码
用双下标原地压缩删除重复字符,看字符串结尾 '\0' 如何收尾。
读指针 r 扫描原串,写指针 w 只收首次出现的字符;循环到 '\0' 停止后,必须手动写 s[w]='\0',否则尾部残留旧字符。
手推一遍压缩过程
从左到右看每个箭头:r 走到哪个字符,判断重复后决定写入 w 或跳过。
分类计数的思想
前面统计成绩时,你写了一串 if:90 分加一、80 分加一……分支越写越多。有没有想过,分数本身就指着一行格子?这一页讲一个更聪明的做法。
客人的房间号对应数据的类别,进门住下对应计数加一
统计字符代码
一次遍历字符串,用计数数组按类别累加,看看各字符归到哪一桶。
counts 数组就是四个桶,每个字符判断类别后让对应下标自增,一次遍历完成全部统计。
自测:统计字符
检验对分类条件与计数初始化的理解
矩阵相乘的规则
前面我们用一维数组统计成绩、去重、计数。现在把一维数组竖起来再排一排,就成了矩阵。两个矩阵能不能相乘、怎么相乘,规则只有一句话:内维相等,行列对应相乘再求和。
菜单行对应订单列,逐项单价乘数量再求和
乘法过程图解
看C行如何与A列逐对相乘再累加:抓住行列相遇点和sum的推进。
三重循环实现
用三重 for 循环把矩阵乘法规则翻译成代码,看清三层各管什么。
i、j 锁定结果 c[i][j] 的位置,k 扫描一行乘一列并累加——三层循环各司其职,次序不能乱。
易错点辨析
三个坑杀伤力最大:下标反了、内维不等、累加没清零。左右对照一次看懂错在哪、怎么改。
- 写 a[j][i],行列下标搞反
- 内维不相等也直接相乘
- sum 在外层循环外只初始化一次
- a[i][j],i 管行、j 管列
- 先检查 A 列数 == B 行数
- sum 在最内层循环前清零
数组应用总结
- ✓所有套路起点都是遍历,先想清下标含义再写
- ✓计数类:一个下标扫,哈希式数组做桶
- ✓原地压缩:双下标读写分离,空间省一半
- ✓多层数据叠加:循环层数=问题嵌套深度
- ✓边界 lastIndex、越界、空数组先想后写
课后思考
三个问题没有标准答案,先自己想十分钟,再对照参考思路。
参考答案往「减少重复遍历」想:同一趟循环里每个元素顺手做三件事,数据只读一遍。关键是每个 if 各管一件事,逻辑没搅在一起,所以既省了次数又不牺牲可读性。
参考答案往「数组套数组」想:一门课是一个数组,多门课就是二维数组。内层循环算单门的和与最值,外层循环遍历课程——和矩阵相乘的双层结构是同一套思路。
参考答案可以先用排序再压缩(代价 O(n log n)),也可以用辅助数组或哈希表记录「见过没有」(用空间换时间,一趟搞定)。比较三种方案在时间和空间上的取舍。