最近我遇到了一个问题，要求在没有任何额外缓冲区的情况下找出字符串中的非唯一字符。我将此问题解释为对字符串中的字符进行就地排序，然后遍历它以追踪非唯一字符。
另一种可以具有 O(1) 空间和 O(n^2) 运行时间的解决方案是使用两个“for”循环遍历字符串以追踪任何常见字符对。
我需要的是在至少 O(nlogn) 时间内用 O(1) 空间对字符串进行排序。
有没有一种简单/优雅的方法可以在 O(nlgn) 中使用 O(1) 空间对字符进行就地排序？
最佳答案
如何，而不是排序，只是扫描字符串来查找出现不止一次的字符？您可以使用 256 位来跟踪哪些字符出现一次，并使用额外的 256 位来跟踪至少出现两次的字符。总的额外内存使用量为512位，仅16个32位字，算法以线性时间运行，不修改原始字符串。
关于algorithm - 对字符串进行就地排序以查明是否存在非唯一字符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4229673/