Array algorithms: max, count, search, average · 数组算法:最大值、计数、查找、平均值
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
Common array jobs
- Some array tasks come up again and again: find the sum, the biggest, the smallest, or count items.
- Each one uses the same idea: start with a guess, then loop and update it.
- These patterns appear all the time on the AP CSA exam.
中文
常见的数组任务
- 有些数组任务一次又一次地出现:求和、求最大值、求最小值,或计数。
- 每一个都用同一个思路:先给一个初始猜测,然后循环并不断更新它。
- 这些模式在 AP CSA 考试里经常出现。
English
Sum and count
- Keep a running total that starts at 0, and add each value.
- To count items that pass a test, start a counter at 0 and add 1 when the test is true.
- Below we count how many values are even (
v % 2 == 0).
中文
求和与计数
- 保留一个从 0 开始的累加总和,并把每个值加进去。
- 要统计通过某个条件的元素,就让计数器从 0 开始,当条件为真时加 1。
- 下面我们统计有多少个值是偶数(
v % 2 == 0)。
public class Main {
public static void main(String[] args) {
int[] a = {3, 4, 7, 10};
int evens = 0;
for (int v : a) {
if (v % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
English
Find the maximum
- Start by guessing the first value is the biggest:
int max = a[0];. - Loop through the rest. If a value is bigger than
max, make it the newmax. - This works for negative numbers too, because the guess comes from the array itself.
中文
求最大值
- 先猜第一个值是最大的:
int max = a[0];。 - 循环遍历其余的值。如果某个值比
max大,就让它成为新的max。 - 这对负数也有效,因为初始猜测来自数组本身。
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
System.out.println(max); // 9
}
}
English
Find the minimum
- The minimum uses the same shape — just flip the test to
<. - Start with
int min = a[0];and keep the smallest value you see. - Never start
minat 0; a real value from the array is a safe first guess.
中文
求最小值
- 最小值用同样的结构 —— 只要把条件改成
<就行。 - 从
int min = a[0];开始,保留你见到的最小的值。 - 永远不要让
min从 0 开始;用数组里一个真实的值作为初始猜测才安全。
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
System.out.println(min); // 2
}
}
English
Search for a value
- To find where a value is, loop the index and compare each element.
- Return the index as soon as you find it.
- If the loop finishes with no match, return
-1to mean "not found".
中文
查找一个值
- 要找出一个值在哪里,就循环下标并逐个比较元素。
- 一找到就返回它的下标。
- 如果循环结束都没找到,就返回
-1表示“未找到”。
English
中文
public class Main {
public static void main(String[] args) {
int[] a = {5, 8, 13, 21};
int target = 13;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // 在第一个匹配处停止
}
}
System.out.println(found); // 2
}
}
English
Average
- Average = sum divided by count. The count is
a.length. - To get a decimal, divide by
(double) a.length, so the math is not integer division. (double)turns the length into a decimal before the division.
中文
求平均值
- 平均值 = 总和 除以 个数。个数就是
a.length。 - 要得到小数,就除以
(double) a.length,这样运算就不是整数除法。 (double)在除法之前把长度变成一个小数。
public class Main {
public static void main(String[] args) {
int[] a = {2, 3, 10};
int total = 0;
for (int v : a) {
total = total + v;
}
double avg = total / (double) a.length;
System.out.println(avg); // 5.0
}
}
English
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past
a.length - 1.
中文
常见错误
- 求最大或最小从第一个元素开始,再和其余比较。
- 不要读过
a.length - 1。
English
Now you try
- Each task completes a method the Harness calls with several arrays.
- Reuse the patterns above: a running total, a "best so far", or a counter.
- Press Run to compile, then Check answer.
中文
现在轮到你
- 每个任务要补全一个方法,Harness 会用多个数组来调用它。
- 复用上面的模式:累加总和、“目前为止的最佳值”,或计数器。
- 按运行来编译,然后按检查答案。
Explore · 探索
Scanning an array for the max · 扫描数组找最大值
One pass keeps a running max, updating it when a bigger value appears. · 一次遍历保存当前最大值,遇到更大的就更新。
Complete max(int[] a) so it returns the largest value in the array. You may assume the array has at least one value. It must work with negative numbers too. · 完成 max(int[] a),让它返回数组里最大的值。你可以假设数组至少有一个值。它对负数也必须有效。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete countEven(int[] a) so it returns how many values are even. A value is even when v % 2 == 0. An empty array returns 0. · 完成 countEven(int[] a),让它返回有多少个值是偶数。当 v % 2 == 0 时,该值是偶数。空数组返回 0。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete indexOf(int[] a, int target). Return the index of the first · 第一个 time · 时间 target appears. If it is not in the array, return -1. · 完成 indexOf(int[] a, int target)。返回 target 第一次出现的下标。如果它不在数组里,就返回 -1。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete average(int[] a). Return the average of the values as a double. Divide by (double) a.length so you get a decimal, not integer division. You may assume the array is not empty. · 完成 average(int[] a)。把这些值的平均值作为 double 返回。除以 (double) a.length,这样你得到的是小数,而不是整数除法。你可以假设数组不是空的。
Click Run to see the output here. · 点击“运行”查看此处输出。