На месте сортировки строки, чтобы выяснить, есть ли неуникальные символы

Question

Недавно я столкнулся с проблемой, которая просит найти неуникальные символы в строке без дополнительного буфера.Я интерпретировал эту проблему как сортировку символов в строке на месте, а затем перебрал ее, чтобы отследить неуникальные символы.

Другое решение, которое может иметь пробел O (1) иO (n ^ 2) во время выполнения имеет два цикла for, проходящих по строке, чтобы отследить любые общие пары символов.

Мне нужно отсортировать строку по крайней мере O (nlogn)) время с пробелом O (1).

Существует ли простой / элегантный способ выполнить сортировку символов на месте в O (nlgn) с пробелом O (1)?

Answer 1

Как насчет сортировки, вместо того, чтобы просто сканировать строку, чтобы найти символы, встречающиеся более одного раза?Вы можете использовать 256 бит, чтобы отслеживать, какие символы встречаются один раз, и дополнительные 256 бит, чтобы отслеживать символы, которые встречаются, по крайней мере, дважды.Общее использование дополнительной памяти составляет 512 бит, всего 16 32-битных слов, и алгоритм работает за линейное время и не изменяет исходную строку.

Answer 2

В википедии есть действительно хорошая таблица сравнения алгоритмов сортировки.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Heapsort и Smoothsort кажутся вашими очевидными победителями. В зависимости от вашего языка у вас могут быть или не быть их, хотя я уверен, что в большинстве случаев они, вероятно, находятся вдали от библиотеки.

Существует Java, который с первого взгляда заявляет, что может сортировать набор чего-либо сопоставимого.
http://www.java -tips.org / Java-SE-советы / java.lang / кучная сортировка реализация в-java.html

Answer 3

Shell Sort.