Алгоритмы: практика
Прежде чем писать программу, прикиньте, сколько работы делает очевидное решение. Двойной цикл по 100000 чисел — это 10 миллиардов шагов, и Python будет считать часами. Тогда нужен прием из этой главы.
Упорядоченные данные — повод для двоичного поиска и двух указателей. Много вопросов про суммы отрезков — для префиксных сумм. Если порядок не важен, данные часто стоит сначала отсортировать.
a = [7, 1, 5, 3]
a.sort()
print(a)
left, right = 0, len(a) - 1
print(a[left] + a[right])
Итог главы. Сортировки выбором и пузырьком делают около n² шагов, слиянием — около n · log n, а подсчет проходит список один раз, когда разных значений мало.
Двоичный поиск находит число или границу в упорядоченном списке и подбирает ответ-число за log n шагов. Префиксные суммы отвечают на вопросы про отрезки сразу, а два указателя проходят список один раз.
В следующей главе — ошибки и проверки: try и except, чтобы программа не падала на неверном вводе.
Урок пройден
Алгоритмы: практика
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Алгоритмы: практика
Практика главы «Алгоритмы»: выбор приема — двоичный поиск, скользящее окно, два указателя, сортировка событий. В 6 заданиях вы найдете ближайшие числа, окно с наибольшей суммой, пары с ограничением на сумму, кусок строки без повторов, самый загруженный момент и прочитаете программу: что она выведет?