sc_*_*ray 0 language-agnostic sorting algorithm in-place
最近我遇到了一个问题,要求在没有任何额外缓冲区的情况下找出字符串中的非唯一字符.我将此问题解释为字符串中的字符的就地排序,然后迭代它以便跟踪非唯一字符.
另一个可以具有O(1)空间和O(n ^ 2)运行时间的解决方案是在字符串上有两个"for"循环来跟踪常见的任何字符对.
我需要的是用O(1)空格在至少O(nlogn)时间对字符串进行排序.
是否有一种简单/优雅的方法在O(nlgn)中使用O(1)空间进行就地排序的字符？
怎么样,而不是排序,只是扫描字符串,找到不止一次出现的字符？您可以使用256位来跟踪哪些字符出现一次,另外256位用于跟踪至少出现两次的字符.额外内存总使用量为512位,只有16个32位字,算法以线性时间运行,不会修改原始字符串.