B*****p
发帖数: 339 | 1 Given a sorted array of strings which is interspersed with empty strings,
write a meth-
od to find the location of a given string
如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
多谢 | y****n
发帖数: 579 | 2 说个傻傻的办法，扫描一遍，把非空的拷出来再做。
或者in place的挪成紧凑数组。 | g*******y
发帖数: 2114 | 3 那不也是O(n)吗
【在 y****n 的大作中提到】
: 说个傻傻的办法，扫描一遍，把非空的拷出来再做。
: 或者in place的挪成紧凑数组。
| I**A
发帖数: 2345 | 4 随便扔砖头
这个题目说的不是很清楚
如果emptry string出现的次数不可以当成常量来看的话，假定是m,then the complexity is O(lg(n)+m)?
如果可以当成常量来看，就还是O(lg(n))。如果是空，可以检测它两侧。。。
【在 B*****p 的大作中提到】
: Given a sorted array of strings which is interspersed with empty strings,
: write a meth-
: od to find the location of a given string
: 如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
: 多谢
| f********3
发帖数: 38 | 5 careercup 上有这个题 的答案
如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
search(int start,int end){
mid=(start+end)/2;
while(str[mid]==' ') {mid++;}
r=strcmp(str1[mid+1,mid+1+str2.length()],str2);
if(r==0) return mid;
else if(r<0) search(mid+1,end);
else search(start,mid-1);
} |
|
