Array algorithms: max, count, search, average
Распространенные задачи с массивами
- Некоторые задачи с массивами повторяются: найти сумму, наибольшее, наименьшее значение или подсчитать элементы.
- Каждая из них использует одну и ту же идею: начните с предположения, затем пройдите цикл и обновите его.
- Эти паттерны часто встречаются на экзамене AP CSA.
Сумма и подсчет
- Ведите накопительную сумму, которая начинается с 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
}
}
Найти максимум
- Начните с предположения, что первый элемент — самый большой:
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
}
}
Найти минимум
- Минимум использует ту же структуру — просто измените условие сравнения на
<. - Начните со значения
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
}
}
Поиск значения
- Чтобы найти где находится значение, пройдите по индексам и сравните каждый элемент.
- Верните индекс, как только найдете совпадение.
- Если цикл завершился без совпадений, верните
-1, чтобы означать "не найдено".
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; // stop at the first match
}
}
System.out.println(found); // 2
}
}
Среднее арифметическое
- Среднее = сумма, делённая на количество. Количество равно
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
}
}
Распространенные ошибки
- Начните поиск максимума или минимума с первого элемента, затем сравнивайте остальные.
- Не выходите за пределы индекса
a.length - 1.
Теперь попробуйте сами
- Каждая задача завершает метод, который Harness вызывает с несколькими массивами.
- Используйте вышеописанные шаблоны: накопительную сумму, «лучший на данный момент» или счётчик.
- Используйте Check answer (Проверить ответ), чтобы скомпилировать ваш код с предоставленными тестами и посмотреть результаты. Сохраните интерфейс класса и метода, показанный в стартере.
Scanning an array for the max
One pass keeps a running max, updating it when a bigger value appears.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Complete indexOf(int[] a, int target). Return the index of the первый время target appears. If it is not in the array, return -1.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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.
Нажмите Запустить, чтобы увидеть результат здесь.