algorithm - 对字符串进行就地排序以找出是否有非唯一字符

Question

最近我遇到了一个问题，要求在没有任何额外缓冲区的情况下找出字符串中的非唯一字符。我将此问题解释为字符串中字符的就地排序，然后遍历它以追踪非唯一字符。

另一个可以有 O(1) 空间和 O(n^2) 运行时间的解决方案是让两个“for”循环遍历字符串以追踪任何常见的字符对。

我需要的是在至少 O(nlogn) 时间内用 O(1) 空间对字符串进行排序。

是否有一种简单/优雅的方法可以在 O(nlgn) 中使用 O(1) 空间进行就地排序？

score 5 · Accepted Answer

怎么样，而不是排序，只是扫描字符串以查找不止一次出现的字符？您可以使用 256 位来跟踪出现一次的字符，并使用额外的 256 位来跟踪至少出现两次的字符。总额外内存使用量为 512 位，仅 16 个 32 位字，算法以线性时间运行，不修改原始字符串。

score 2 · Accepted Answer

维基百科上有一个非常好的排序算法比较网格。

Heapsort和Smoothsort似乎是你明显的赢家。根据您的语言，您可能已经拥有也可能没有这些，尽管我确信在大多数情况下它们可能在图书馆之外。

有一个 Java impl 一目了然地声称可以对一组任何 Comparable 进行堆排序。
http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html

score 0 · Accepted Answer

0

于 2010-11-19T21:53:10.583 回答

3 回答 3