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

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

overview:construct a nested loop, compare ith char to i+1, i+2,...,nth char in that string.
if any of comparision matches, return false. return true when loops end.

https://gist.github.com/edussx/4970428

https://gist.github.com/Sayary/4970488

In Java language.
Build a nested loop to to traversal the string and use charAt() to get the byte of each index.
Time complexity is O(n*n).

edussx 发表于 2013-2-17 14:19
overview:construct a nested loop, compare ith char to i+1, i+2,...,nth char in that string.
if any ...

这个是O(n^2)的，令N=max(n,charsetnum)，这个题目最好的复杂度应该是O(N)的，当然O(NlogN)的方法也很好想。就是不知道额外的数组算不算additional data structures了。期待更精彩的解答哦~

lvchaoshuai 发表于 2013-2-17 14:59
这个是O(n^2)的，令N=max(n,charsetnum)，这个题目最好的复杂度应该是O(N)的，当然O(NlogN)的方法也很好想 ...

复杂度还没学到，所以没想过这方面的问题

额外的数组如果算additional data structures的话，在c++里可以使用at() member function,即s.at(i)来代替s[i]

edussx 发表于 2013-2-17 14:19
overview:construct a nested loop, compare ith char to i+1, i+2,...,nth char in that string.
if any ...

Wow, so quick! If we can not use additional data structures, then it seems we have to do the brute force search(or maybe there exists a better solution, unfortunately I'm not clever enough to figure it out).

But if it's not, and if all the characters in the string fall into a alphabet, we can create a bitmap. Even in the extreme situation, we have unicode as our alphabet, which contains slightly more than 1M characters, we will only consume very little memory, like 122KB. And the algorithm runs on it only takes O(n) steps.

edussx 发表于 2013-2-17 15:10
复杂度还没学到，所以没想过这方面的问题

额外的数组如果算additional data structures的话， ...

不是，暂时还没想到不用额外数组的O(n)方法，不知道是否存在=.=

Algorithm_1: There are two cycles and everytime pick one element of string to compare with the rest chacteristics of the string.
Algorithm_2: First of all, sort the string; then compare every element with any elements before or behind it
试一试。
https://github.com/Tedatworking/ ... ster/20130217_1.cpp

edussx 发表于 2013-2-17 14:19
overview:construct a nested loop, compare ith char to i+1, i+2,...,nth char in that string.
if any ...

恩恩，正解，不知道有没有在不增加数据结构的情况下的O(n)算法

https://gist.github.com/cqx83/4970678