算法题哦

luffy.deng

原帖由 satoru 于 2009-3-19 09:26 发表


对不起
我刚才没有讲清楚
我的理解是：
  如果使用遍历一个长度为 n 的字串中的每一个字符
  并且对其中每个不重复的字符调用一次count，
  那么最坏的情况下(字串中所有字符都是不同的),
  复杂度就 ...

确实是这样，好事直接遍历一次好。

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. 
    

复制代码

hitsubunnu

统计一个字符串里面出现次数最多的字符

1. 
   
2. use List::Util qw(max);
   
3. 
   
4. my $str = 'hellooloooooo';
   
5. my (%h,%f);
   
6. 
   
7. $f{++$h{$_}}=$_ for split //,$str;
   
8. 
   
9. print $f{max keys %f};
   

复制代码

[ 本帖最后由 hitsubunnu 于 2009-3-19 10:31 编辑 ]

teebye

原帖由 hitsubunnu 于 2009-3-19 10:29 发表



use List::Util qw(max);

my $str = 'hellooloooooo';
my (%h,%f);

$f{++$h{$_}}=$_ for split //,$str;

print $f{max keys %f};

看不懂perl的，不妨看看ruby怎么实现的

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def count(a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result =[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.uniq.each do|x| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result << [x,a.grep(x).length] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.max { |a, b| a[1]<=>b[1] } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s = "aadddeegggggg" str = s.scan(/w{1}/) p count(str)

dreamerx2004

原帖由 DQP 于 2009-3-19 09:01 发表


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

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

DQP

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



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

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

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

efhilt

人家楼主把题目改了。

efhilt

正如真理总是赤裸裸的，真相也总是血淋淋的。我之所以不能再用shhgs这个名字，充分验证了我的签名的正确性。

efhilt

是错了。

如果要遍历就没有意思了。

victorlee129

1. 
   
2. s=raw_input();
   
3. print s[s.index(max([s.count(i) for i in s])];
   

复制代码

手边没py也许不对