[第二轮] 2/18-2/24 CareerCup 1.1

sunnyroom 发表于 2013-2-18 22:21
用了最笨的办法，每个字符循环比较。时间，空间复杂度什么的，还不知道怎么算，明天学习一下，然后看一下大 ...

可以先排序，再比较吧。
不排序的话，时间复杂度O(N^N),排序的话，排序是O（n lgn），比较是O（N）

Compare the 1st char in a string with 2nd to the last; then compare the 2nd with 3rd to the last................ If two char are the same, then return FALSE.

https://gist.github.com/lazyGoose/4978681

jerrysun 发表于 2013-2-18 19:34
https://gist.github.com/JerrySun363/0c7fb3b4d9c54aa41171

其实不是很清楚能用什么样的API

学习了...
HashSet does not allow duplicates.

https://github.com/swang1022/car ... 1.1/hasUniqChar.cpp
idea: sort the string first then compare adjacent character

bitmap的方法还不是太懂，学习中~

https://gist.github.com/bigteeth/4981284

Using the Bitmap is a better way to implement it. The running time is O(N).

jerrysun 发表于 2013-2-18 19:34
https://gist.github.com/JerrySun363/0c7fb3b4d9c54aa41171

其实不是很清楚能用什么样的API

第一个HashSet的时间复杂度是O(n)?  hashset.add 不要考虑？

lazyGoose 发表于 2013-2-19 00:43
Compare the 1st char in a string with 2nd to the last; then compare the 2nd with 3rd to the last.... ...

大多数人都是这么写的。
我还忘了string.length()-1

https://github.com/knightelvis/a ... niqueCharacter.java
Two implementations. One is using bitmap and the other one is using sorting and comparing.

https://gist.github.com/Toanso/4984819

sunnyroom 发表于 2013-2-19 15:25
第一个HashSet的时间复杂度是O(n)?  hashset.add 不要考虑？

HashSet Add操作是O(1)的，N个元素是O(N)的