如何查找字符串中第一个重复字符

撞墙的猪

如：“hello world”中 的 l
“my name is Amen”中的 m

要求O(n)

hellioncu

建立一个256的数组A，初始都为0，取每个字符c，若A[c]==0则A[c]=1，反之c就是要的结果

雨过白鹭洲

楼上说的是传说中的bitmap

liexusong

2楼的方法不错, 不过要预处理, 预处理的时间可能比较长, 我觉得如果是查找一个字符的话, 直接去搜索也挺快的

cobras

2楼的方法是最佳的了。

1. 
   
2. /* rptchr.c */
   
3. 
   
4. #include <stdio.h>
   
5. #include <string.h>
   
6. 
   
7. int repeat_char(const char *s)
   
8. {
   
9.         char map[256];
   
10.         unsigned char c;
    
11. 
    
12.         memset(map, 0, sizeof(map));
    
13.         while ((c = *s++) != '\0') {
    
14.                 if (map[c]) {
    
15.                         return c;
    
16.                 }
    
17.                 ++map[c];
    
18.         }
    
19.         return -1;
    
20. }
    
21. 
    
22. int show_first_repeated_char(const char *s)
    
23. {
    
24.         int c;
    
25. 
    
26.         c = repeat_char(s);
    
27.         if (c == -1) {
    
28.                 printf("string %s don't have any repeated characters\n", s);
    
29.                 return -1;
    
30.         }
    
31.         printf("first repeated character of string \"%s\" is '%c'\n", s, c);
    
32.         return 0;
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.         show_first_repeated_char("hello world");
    
38.         show_first_repeated_char("my name is Amen");
    
39.         return 0;
    
40. }
    

复制代码

srdgame

《编程珠玑》