Array algorithms: max, count, search, average · 数组算法:最大值、计数、查找、平均
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
数组的四个经典任务
- 大多数数组操作都是四种扫描之一:找最大值、计数、查找某个值,或求平均值。
- 每一种都是对数组的一次
for循环,加上一个记住某样东西的变量。 - 一旦掌握了这四种,大多数数组问题都只是在其中之一上做点小改动。
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
找最大值
- 先假设第一个元素最大:
int best = a[0];。 - 然后看其余的。如果某个元素比
best大,它就成为新的best。 - 这对负数也成立,因为你是从一个真实的元素开始,而不是从
0。
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
带条件的计数
- 计数器从
0开始,每当一个元素通过判断就加1。 - 比如,在循环里用
a[i] % 2 == 0来数偶数。 - 计数器最终的值就是你的答案。
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
线性查找
- 要查找,就遍历数组,把每个元素和目标比较。
- 一找到匹配就立刻返回它的下标。如果循环结束都没找到,就返回
-1。 -1是常用的“没找到”信号,因为它永远不是合法的下标。
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
避免整数除法错误的平均值
- 把所有元素加进一个
int总和,然后除以n。 - 两个
int相除会丢掉小数,所以要强制转换:(double)total / n。 - 返回
double,让调用者得到精确的平均值。
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
常见错误
- 求最大或最小从第一个元素开始,再和其余比较。
- 不要读过数组末尾。
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
现在轮到你了
- 传入数组和它的长度
n,为每个任务选对那个“记住”的变量。 - 不要自己写
main—— 检查器会提供。
Scanning an array · 扫描数组
One pass keeps a running result (max, sum, count) across the array. · 一次遍历在整个数组上保存一个累计结果(最大值、和、计数)。
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not · 不 write a main. · 完成 int max(const int a[], int n),让它返回最大的元素(假设 n >= 1)。从 a[0] 开始,这样负数也能正确处理。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not · 不 write a main. · 完成 int count_even(const int a[], int n),让它返回有多少个元素是偶数。用 % 2。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not · 不 write a main. · 完成 int index_of(const int a[], int n, int target),让它返回第一个 target 的下标;如果不存在则返回 -1。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not · 不 write a main. · 完成 double average(const int a[], int n),让它返回元素的平均值(假设 n >= 1)。用强制转换避免整数除法。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。