优化Unique Characters?

题目在此：http://www.lintcode.com/en/problem/unique-characters/

这题虽然非常简单，想知道到底还能优化到什么程度。

非常容易就能用HashSet解决。

题目说，不用额外空间，那就想到用时间换空间，时间多点，o(n^2)，就不需要额外空间。

想知道，这题，你们还能想到其他更优的不用额外空间的解法吗？ 多谢讨论


我的代码在此链接的第47，48楼。http://www.1point3acres.com/bbs/thread-135921-3-1.html

对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

感谢回复哈。

从你的回复，我巩固了 radix sort
https://en.wikipedia.org/wiki/Radix_sort

2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

你能实现其中一种吗？java的就最好了。

我直接看代码比较直观。多谢啦

love1point 发表于 2015-6-16 19:00
你能实现其中一种吗？java的就最好了。

我直接看代码比较直观。多谢啦

mergesort之类的难道不是网上一抓一把么

不过   
string在java,python里面都是immutable的
所以并没有什么卵用
还是需要额外空间来排序
然后就大材小用搞复杂了  反而没什么意思
不如就hash了

其他我就不懂了哦  单纯看这个题目觉得好像没什么意思

2015fallcser 发表于 2015-6-19 18:37
mergesort之类的难道不是网上一抓一把么

不过   

用hash，需要额外空间

不用额外空间，双循环

我好奇，有没有，不需要额外空间，且时间复杂度是o（n）的

love1point 发表于 2015-6-19 18:41
用hash，需要额外空间

不用额外空间，双循环

不是说了么
immutable的，无法操作

如果是char[]的话，
排序一遍，去重一遍（这不就是hash么）
然后比较一遍  
最好的情况是linear  （O(2m+2n+min(m,n))）
不过真的感觉毫无毫无意义

当然可能有意义的我没想到  **表示就不乱指路了

2015fallcser 发表于 2015-6-19 18:54
不是说了么
immutable的，无法操作

谢谢回答。

我知道，我的好奇是问大家，给看这个帖子的其他人，我知道你已经回复我了，谢谢了

2015fallcser 发表于 2015-6-15 19:19
对每个字母按照ASCII值排序
logarithmic: quicksort, mergesort
linear: radix sort了

radix sort需要额外空间

kittycerry 发表于 2015-6-23 14:59
radix sort需要额外空间

你有啥好解法吗