Реализация алгоритмов с массивами
| English | Русский |
|---|---|
| traversal/træˈvɜːsl/ | обход |
| index/ˈɪndeks/ | индекс |
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
Стандартные алгоритмы для массивов
- Большинство задач с массивами представляют собой обход плюс один из нескольких стандартных шаблонов.
- Сумма / среднее: накопите общую сумму, затем разделите на
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}: максимум станет равен9.
Алгоритмы работы с массивами сочетают проход с шаблоном: сумма/среднее, подсчёт, минимум/максимум или поиск (возвращает индекс или -1). Инициализируйте минимум/максимум первым элементом, а не 0. Изменение элементов требует индексированного цикла, а чтение a[i+1] требует более строгой верхней границы для выхода за допустимые пределы.
Поиск максимума
max начинается с a[0]=3, становится 9, затем остается неизменным (a = {3,9,5}).
Чтобы найти максимум массива, вы должны инициализировать max как...
Начало с 0 даст ошибку, если все значения отрицательны.
Для a = {3, 9, 5}, каково максимальное значение?
9 — наибольший элемент.
Линейный поиск возвращает, что если цель не найдена?
По конвенции -1 означает «не найдено».
Алгоритм, который читает a[i+1], должен работать, пока...
Остановка на один шаг раньше сохраняет a[i+1] в пределах границ.
Изменение элементов массива (a[i] = ...) требует индексированного цикла, а не for-each.
for-each не может записывать обратно в массив.