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

Question

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

要求O(n)

Answer 1

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

Answer 2

楼上说的是传说中的bitmap

Answer 3

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

Answer 4

2楼的方法是最佳的了。

2. /* rptchr.c */
4. #include <stdio.h>
5. #include <string.h>
7. int repeat_char(const char *s)
8. {
9.         char map[256];
10.         unsigned char c;
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. }
22. int show_first_repeated_char(const char *s)
23. {
24.         int c;
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. }
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. }

复制代码

Answer 5

《编程珠玑》