对字符串进行就地排序以查找是否存在非唯一字符
最近我遇到一个问题，要求在没有任何额外缓冲区的情况下找出字符串中的非唯一字符。我将这个问题解释为对字符串中的字符进行就地排序，然后迭代它以追踪非唯一字符。
另一种具有 O(1) 空间和 O(n^2) 运行时间的解决方案是使用两个“for”循环遍历字符串来跟踪任何常见的字符对。
我需要的是在至少 O(nlogn) 时间内使用 O(1) 空间对字符串进行排序。
有没有一种简单/优雅的方法可以在 O(nlgn) 和 O(1) 空间中对字符进行就地排序？
Recently I came across a problem that asks to find out the non-unique characters in a string without any additional buffer. I interpreted this problem to be an in-place sort of the characters in the string and then iterating through it in order to track down the non-unique characters.
Another solution that can have O(1) space and O(n^2) run-time is having two 'for' loops going over the string to track down any pairs of characters that are common.
What I need is to sort the string in atleast O(nlogn) time with O(1) space.
Is there a simple/elegant way to do an in-place sort of characters in O(nlgn) with O(1) space?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
不排序，只扫描字符串来查找多次出现的字符怎么样？您可以使用 256 位来跟踪哪些字符出现一次，并使用额外的 256 位来跟踪至少出现两次的字符。总共额外使用的内存为 512 位，仅 16 个 32 位字，算法以线性时间运行，并且不会修改原始字符串。
How about, rather than sorting, just scanning the string to find the characters that occur more than once? You can use 256 bits to keep track of which characters occur once, and an additional 256 bits to keep track of the characters that occur at least twice. Total extra memory usage is 512 bits, just 16 32-bit words, and the algorithm runs in linear time, and does not modify the original string.
维基百科上有一个非常好的排序算法比较网格。
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
There is a really nice comparison grid of sorting algorithms on wikipedia.
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
Heapsort and Smoothsort seem to be your obvious winners. Depending on your language you may or may not already have these, though I'm sure in most cases they're probably a library away.
There's a Java impl that at a glance claims to heapsort a set of anything Comparable.
http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html
希尔排序。
Shell Sort.