對字符串進行排序以確定是否存在非唯一字符

Question

最近我遇到了一個問題，要求查找字符串中的非唯一字符而沒有任何附加緩衝區。我將這個問題解釋爲字符串中的字符就地排序，然後遍歷它以追蹤非唯一字符。

另一種可以具有O（1）空間和O（n^2）運行時的解決方案是通過兩個'for'循環遍歷字符串來追蹤任何常見的字符對。

我需要的是在至少O（nlogn）時間用O（1）空間對字符串進行排序。

是否有一種簡單/優雅的方式來執行O（nlgn）中具有O（1）空間的就地排序字符？

Answer 1

有維基百科上的排序算法的一個非常好的比較網格。

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

堆排序和Smoothsort似乎是個明顯的贏家。根據您的語言，您可能已經或可能不會擁有這些語言，儘管我確信在大多數情況下他們可能已經離開了圖書館。

有一個Java impl，一眼就聲稱可以包含一組Comparable。
http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html

Answer 2

Shell Sort.

Answer 3

怎麼樣，而不是排序，只是掃描字符串，以找到不止一次出現的字符？您可以使用256位來跟蹤哪些字符出現一次，還可以使用另外的256位來跟蹤至少出現兩次的字符。額外內存總使用量爲512位，只有16個32位字，算法運行時間爲線性，不會修改原始字符串。