Сортировка массива символов

Question

Вот вопрос интервью, который у меня был.

Ввод: строка символов (ASCII) может быть предложением. Могут дублироваться. Выход: отсортированных в порядке ASCII значения

Ожидаемая сложность: Линейное время и постоянное дополнительное пространство

Моя мысль была сделать тип ведром сортировки, где у вас есть массив размером 256 и затем использовать, но если у вас есть дубликаты, тогда как это сработает? Будет ли это считаться постоянным пространством? Я думаю, это было бы потому, что вы только когда-либо использовали массив размером 256, и что он не будет расти с размером ввода.

Не хочу, чтобы конкретный код, как я хотел бы сделать это сам, но любые подсказки были бы полезны!

Answer 1

Решение этой проблемы: counting sort.

У вас будет массив размером 128 и все значения будут инициализированы на 0. Используйте значение ascii символа для индексации в массив и затем увеличивайте значение массива.

Сортированная последовательность будет создаваться путем перемещения массива размером 128, где вы печатаете только символ значения ascii i, если массив [i] не равен нулю, а значение дает частоту символа, который будет напечатан ,

Вы правы, это постоянный размер O (1) и алгоритм линейного времени O (N).