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

sjtuzyt 发表于 2013-2-25 17:21
https://gist.github.com/sjtuzyt/5028673

https://gist.github.com/sjtuzyt/5028620

https://gist.github.com/sjtuzyt/5028673 这个就是假设了是ascii码。O(1) space。
题目中，是不使用额外的数据结构？

sing1ee 发表于 2013-3-17 23:46
https://gist.github.com/sjtuzyt/5028673 这个就是假设了是ascii码。O(1) space。
题目中，是不使用额外 ...

这个使用了O(n)的额外空间。它的时间复杂度是O(n)。我写的另外那个用快排的没用额外空间，但时间复杂度是O(nlogn)

sjtuzyt 发表于 2013-3-18 09:11
这个使用了O(n)的额外空间。它的时间复杂度是O(n)。我写的另外那个用快排的没用额外空间，但时间复杂度是 ...

这是常数大小数组，O(1)的空间啊。

sjtuzyt 发表于 2013-3-18 09:11
这个使用了O(n)的额外空间。它的时间复杂度是O(n)。我写的另外那个用快排的没用额外空间，但时间复杂度是 ...

1. #include<iostream>
   
2. #include<string>
   
3. using namespace std;
   
4. int uniquechar(string s);
   
5. int main()
   
6. {
   
7.   string s;
   
8.         cin>>s;
   
9.         if(uniquechar(s)) cout<<"Not Unique"<<endl;
   
10.         else cout<<"Unique"<<endl;
    
11.         return 0;
    
12. }
    
13. int uniquechar(string s)
    
14. {
    
15.         int len=s.length();
    
16.         int num[256];
    
17.         for(int i=0;i<256;i++)
    
18.         {
    
19.                 num[i]=0;
    
20.         }
    
21.         int ans=0;
    
22.         for(int i=0;i<len;i++)
    
23.         {
    
24.                 num[s[i]-'0']++;
    
25.         }
    
26.         for(int i=0;i<256;i++)
    
27.         {
    
28.                 if(num[i]>1)
    
29.                         ans=1;
    
30.         }
    
31.         return ans;
    
32. }

复制代码

这个使用了常数大小的数组。O(1)的空间。
遍历一次原字符串，O(N)时间。

sjtuzyt 发表于 2013-3-18 09:11
这个使用了O(n)的额外空间。它的时间复杂度是O(n)。我写的另外那个用快排的没用额外空间，但时间复杂度是 ...

另外快排那个，栈空间算额外空间么，如果算，就是O(logn)的栈空间。

sing1ee 发表于 2013-3-18 10:11
这个使用了常数大小的数组。O(1)的空间。
遍历一次原字符串，O(N)时间。

这题的改版比较多，这种解法应该是效率最高的。如果用hashtable实现代码可能会更简单一些。如果不让用额外的数据结构来做的话就是O(n^2)，另外如果可以对原输入字符串进行修改，那么sort一下，可以达到O(nlogn)

sing1ee 发表于 2013-3-18 10:13
另外快排那个，栈空间算额外空间么，如果算，就是O(logn)的栈空间。

嗯，第一个的确是O(1),好久前写的了，hash table给我的惯性思维是O(n) 大小的数组。我以前从来不考虑递归产生的栈空间，的确是需要。

https://gist.github.com/5251707.git

two methods in java

假如可以使用外部data structure的话，用hashtable会不会很快，map的时间只需要O(1), 然后每个buckect的record记录是否这个index被查找到过，对string的each character进行hashmap，一旦遇到record!=0的，就表示非unique。这样复杂度是O(n).