3
Leecode(387)
source link: https://luzhijun.github.io/2016/08/28/leecode(387)/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
楚汐|Trucy Luce Blog
从一个字符串中找出第一个非重复字符，输出所在字符串中的位置，如果不存在，输出-1.
难度评价：简单
Examples:
s = “leetcode”
return 0.
s = “loveleetcode”,
return 2.
思路很简单，就是对每个字符计数，然后找出计数为1的字符输出。既然要输出索引，那么就要想办法在计数的时候就把索引信息输进去，千万别用index(x)或者find(x)方法来增大时间开销。
第一种方法，利用Ordereddict. Ordereddict为python中的顺序字典，存储结构为FIFO的链式。
from collections import OrderedDict
def firstUniqChar1(string):
"""
:type s: str
:rtype: int
"""
o=OrderedDict()
for i,s in enumerate(string):
if o.get(s)==None:
o[s]=i
else:
o[s]=-1
for oi in o:
if o[oi]!=-1:
return o[oi]
return -1
上述程序设置OrderedDict初始值都为字符所在索引值，若有重复标记为-1，那么结果中只要查第一个非-1的item即可拿到索引。程序中用OrderedDict保持索引顺序性，但实际上字符串本身就有顺序性，只需要一个普通字典就可以了，以字符串为字典的键，无需OrderedDict这种高昂的结构。
第二种方法，利用collections中的计数字典Counter来替代
from collections import Counter
def firstUniqChar2(string):
char_dict = Counter(list(string))
for i, s in enumerate(string):
if not char_dict[s]-1:
return i
return -1
其实仔细想想字典的键值既然都是字符，那么其ASCII码对应的整数可以用数组索引表示。初始化一个128位的字符数组即可表示所有可能的拉丁字符,对应字典中的键值。
def firstUniqChar3(string):
chars=[0]*128
for s in string:
chars[ord(s)]+=1
for i,s in enumerate(string):
if chars[ord(s)]==1:
return i
return -1
以上三种数据结构虽然都能解决问题，但时间复杂度明显有差距，尤其是第三种。
以”dddccdbba”为例，重复1万次，对应时间做成柱状图如下：
能用数组尽量数组，当键值为整数或者字符的时候，数组完全可以替代字典的功能。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK