Разберём классический алгоритм, который можно расширить для более сложных на примере решения очередной задачи:
В этой задаче требуется просто отсортировать массив (список). Подразумевалось, что массив будет большого размера, и стандартные функции сортировки не будут успевать это сделать за отведённое время.
Однако задача на сайте уже много лет, и компьютеры становятся быстрее, поэтому данную задачу можно очень просто решить даже на Python (точнее на PyPy):
Здесь мы просто считываем данные в список и вызываем встроенную функцию sorted:
sorted(iterable[, cmp[, key[, reverse]]])
Да, сигнатура функции довольно сложная, но если надо просто отсортировать список, то можно не смотреть на необязательные параметры.
Но, написав такое решение, мы ничему новому не научились, а так неинтересно. Давайте подумаем, как же можно было решить задачу иначе?
Важным моментом среди ограничений является то, что числа целые и лежат в очень маленьком диапазоне. И, как следует из названия задачи (которое является подсказкой), можно для каждого числа из входного файла посчитать, сколько раз оно встречается.
И тогда, чтобы вывести исходный список в отсортированном виде, надо пройти по всем числам от -100 до 100 и вывести их столько раз, сколько мы насчитали.
Таким образом мы получим линейное решение (в то время как встроенные алгоритмы сортировки работают за время O(N log N)).
Начнём с ввода данных:
Так как нам нет необходимости хранить размер списка в отдельной переменной, то можно результат первого input'а никуда не присваивать.
Удобство списка в Python заключается в том, что можно использовать отрицательные индексы. Но нам важно, чтобы элементы с отрицательными индексами не влияли на элементы с положительными. Поэтому заведём список на 200+ элементов (всегда делайте с небольшим запасом). В других языках программирования можно было бы ко всем числам прибавить 100, тогда бы их относительный порядок не изменился, а индексы были бы от 0 до 200 включительно.
После этого у нас есть список, в i-ой ячейке которого лежит число - сколько раз число i встречалось во входных данных.
Если выводить данные поэлементно, то это не уложиться в отведённое время, так как работа с внешними устройствами довольно медленная. Поэтому сначала сформируем итоговый список:
Так как i проходит от -100 до 100, то все элементы в списке r будут идти в неубывающем порядке.
И после этого можно уже вывести список целиком:
Это решение ровненько укладывается в ограничение времени. То есть работает медленнее, чем стандартный алгоритм. Это связано с большой константой. Если увеличивать размер входных данных, то, начиная с некоторого момента, данное решение начнёт обгонять функцию sorted.
Осталось заметить, что этот алгоритм является частным случаем поразрядной сортировки. Предположим, что в задаче числа были бы не до 100, а до 100000000. Тогда можно было бы сначала таким способом отсортировать числа по последним двум разрядам, потом по двум предпоследним разрядам и т.д. То есть за четыре применения представленного алгоритма мы бы получили отсортированный список.
На этой же идее работает алгоритм построения суффиксного массива.
Предыдущий выпуск: Задача 12. Дачники
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
