Опять задали вопрос на собеседовании, на который я не сразу дал ответ, а уже вдогонку отправил письмом. Что вы думаете по поводу этого?
Задача: Дан огромный массив чисел, состоящий только из 0, 1 и 2. Описать алгоритм как его отсортировать и оценить сложность алгоритма.
ЗЫ: в каментах ответ, предупреждаю :)
Что я смог придумать:
ОтветитьУдалитьПервым проходом подсчитываем количество 0, 1 и 2.
Вторым, сетим массив.
В нужном порядке, например, с начала 0, потом 1, потом 2. Можно в любом другом порядке.
Чорт :) Сразу отгадал :D
ОтветитьУдалитьУж извините за занудство, но может от вас хотели что-то оттуда http://ru.wikipedia.org/wiki/Алгоритм_сортировки (например, http://ru.wikipedia.org/wiki/Сортировка_подсчетом), и сказать "я отсортирую этот массив за O(n)".
ОтветитьУдалитьхотя это он и есть (сортировка подсчетом) =)
ОтветитьУдалитьЭто можно сделать одним проходом без дополнительных memory allocations. Не спроста дано только три числа:
ОтветитьУдалитьИдея в том, чтобы разделить массив на три блока для чисел 0, 1 и 2. Хранить указатель на конец блока 0 и начало 2. Сделать один проход, где для каждого i-го числа, совать его в соответсвтующий блок, и менять границы блоков по необходимости.
https://gist.github.com/nodirt/5579453