名企笔试：去哪儿2015研发笔试题（首个重复字符）

1、题目要求

 

对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。

给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于500。

---

2、程序分析

 

• 首先要划定字符串里字符的范围，我这里划定范围是ascii码表里的字符常用的128个字符
• 创建一个长度为128的list，所有值设置为0
• 遍历每一个字符，将字符转化为10进制，以这个字符所对应的10进制值作为下角标，如果之前的值为0，则修改1，如果为1，说明在前面已经遇到过这个字符

---

3、示例代码

#coding=utf-8
string = 'qywyer23tdd'
lst = [0 for i in range(128)]
for ch in string:
    index = ord(ch)
    if lst[index] == 0:
        lst[index] = 1
    else:
        print ch
        break