Еще один алгоритм работы-собеседования

Question

Итак, вот вопрос:

Предположим, у вас есть 100 тысяч целых чисел в диапазоне от 1 до 1 миллиона. Пожалуйста, сортируйте целые числа. Временная сложность должна быть O (n).

Любой, кто разделяет его или ее идеи, ценится.

Answer 1

Походит на прямую сортировку счета.

1. Резервирование памяти для массива размером 1 миллион
2. Инициализация всех значений массива в 0
3. Цикл поцелые числа.Для каждого целого числа i увеличиваем a [i] на единицу.
4. Выводим отсортированную последовательность, проходя через массив и печатая каждое число i в течение [i] раз.

Пробел постоянен,Время выполнения O (n).

Answer 2

Намек должен быть от 1 до 1 миллиона.

См. сортировка по голубям

Answer 3

Поскольку задача имеет фиксированный размер и включает в себя конечный набор экземпляров, любой алгоритм сортировки заканчивается в O (1).Вы должны сказать тестеру вернуться в школу анализа алгоритмов.Один из возможных способов обобщить эту проблему на бесконечное множество: у вас есть массив размером n с числами в диапазоне [0, 10n].Можете ли вы отсортировать это в O (N)?Это имеет смысл для меня.Или вы можете параметризовать проблему с размером массива и диапазоном целых чисел и придумать некоторую оценку O (f (n, k)).Проблема в том, что когда вы получаете такой вопрос в интервью, что вы делаете?Вы пытаетесь угадать, что интервьюер хотел бы услышать, или вы говорите что-то вроде «позвольте мне перефразировать ваш вопрос»?Или вы просто идете к выходу с широкой улыбкой?

Answer 4

Вы должны использовать любые известные алгоритмы сортировки со сложностью O (n)

Есть ли алгоритм целочисленной сортировки O (n)?

Answer 5

Использовать сортировку по количеству. Просто посчитайте их все (O (n)), а затем создайте и заполните массив результатов (O (n), снова).