词汇
| English | 释义 | 拼音 |
|---|---|---|
| traversal/træˈvɜːsl/ | 遍历 | biàn lì |
| index/ˈɪndeks/ | 下标 | xià biāo |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
标准数组算法
- 大多数数组任务是一次遍历加上几个标准模式之一。
- **求和 / 平均:**累加一个总和,再除以
length。 - **计数:**当元素满足条件时加一。
- **最小 / 最大:**追踪到目前为止见过的最小或最大值。
找最大值
- 让
max = a[0](第一个元素)开始,然后从下标1遍历。 - 循环里
if (a[i] > max) { max = a[i]; }。 - 循环之后,
max保存数组里最大的值。 - 从第一个元素开始,而非
0——0可能比每个值都大。

逐次追踪查找数组最大值的过程
搜索一个值
- 要检查一个值是否存在,遍历并比较每个元素。
- 返回找到它的下标,或如果循环结束仍无匹配就返回
-1。 - 循环里
if (a[i] == target) return i;;之后return -1;。 - 这是线性搜索(第 4.14 节深入讲它)。
移动与修改
- 有些算法移动或改变元素——如把一切左移,或让每个值翻倍。
- 修改需要带下标循环,好让你能赋值
a[i] = ...。 - 读
a[i+1]时留意边界——最后一个下标没有邻居。 - 仔细追踪下标以避免越界访问。
注意
**用第一个元素、而非 0 初始化最大/最小搜索。**如果每个值都是负数,int max = 0; 会失败(它会错误地报告 0)。用 int max = a[0]; 并从下标 1 开始循环。而当一个算法读 a[i+1] 时,让循环在 i < a.length - 1 停止,否则最后一次迭代会读过末尾。
例子
找 a 的最大值:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- 对
a = {3, 9, 5}:max 变成9。
关键点
数组算法把一次遍历与一个模式组合:求和/平均、计数、最小/最大,或搜索(返回下标或 -1)。用第一个元素、而非 0 初始化最小/最大。修改元素需要带下标循环,而读 a[i+1] 需要更紧的边界以保持在范围内。
探索
找最大值
max 从 a[0]=3 开始,变成 9,然后保持(a = {3,9,5})。
练习
要找数组的最大值,你应把 max 初始化为……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
如果所有值都是负数,从 0 开始会失败。
练习
对 a = {3, 9, 5},最大值是多少?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
9 是最大的元素。
练习
如果目标未找到,线性搜索返回什么?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
按惯例,-1 意思是“未找到”。
练习
一个读 a[i+1] 的算法循环条件应是……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
提前一步停止让 a[i+1] 保持在范围内。
练习
修改数组元素(a[i] = ...)需要带下标循环,而非 for-each。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
for-each 不能赋值回数组。