算法题哦

DQP

原帖由 efhilt 于 2009-3-18 20:16 发表
lambda s : len(set(s)) * 1. / len(s)  > 0.5

居然看到了传说中的shhgs。 审题不错，赞一个。
但你的签名实在让人讨厌。

DQP

LZ的题目本来是判断有没有满足条件的字符
而不是求出那个字符。
大多数人都看错题了 呵呵

通常对于求出在一个列表中出现次数大于总数一半的元素问题。 是可以用一个与快速排序相类似的算法的。

具体到本题 有一个特点不知道大家注意到没有。
这个列表是字符串而元素是字符~~~~
如果这个字符是ASCII字符的话那么一切就都简单了。 因为ASCII总共才128个。
我们可以建立一个长度为128的数组， 用字符的ASCII作为下标， 数组中的元素是出现的次数。

1. 
   
2. #include <stdio.h>
   
3. int main(){
   
4.   int chr_count[128];
   
5.   int len;
   
6.   char str[] = "hellooooooo";
   
7.   char *p = str;
   
8.   memset(chr_count, 0, sizeof(chr_count));
   
9.   while(*p){
   
10.     chr_count[(int)*p]++;
    
11.     p++;
    
12.   }
    
13.   len = p - str;
    
14.   p = str;
    
15.   while(*p){
    
16.     if(chr_count[(int)*p] > (len + 1)/ 2){
    
17.       printf("%c\n", *p);
    
18.       return 0;
    
19.     }
    
20.     p++;
    
21.   }
    
22.   return 0;
    
23. }
    
24. 
    

复制代码

DQP

原帖由 dreamerx2004 于 2009-3-19 22:44 发表



真的不错吗？我觉得他的算法是错误的吧？Please advice..

是哈。 是错的。。。。。。。
我自杀了算了

[ 本帖最后由 DQP 于 2009-3-19 23:23 编辑 ]