赞
踩
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
【示例】
s = “leetcode”
返回 0
s = “loveleetcode”
返回 2
提示:你可以假定该字符串只包含小写字母。
遍历两边数组,第一遍统计每个字符出现的次数,并把统计结果保存到新数组中。第二遍遍历数组时,如果当前字符出现次数刚好为1,则返回当前索引,若未找到,返回-1.
class Solution { public: int firstUniqChar(string s) { vector<int> counts(26, 0); int index = -1; for (int i=0; i<s.size(); ++i){ if (counts[s[i]-'a'] < 2){ ++counts[s[i]-'a']; } } for (int i=0; i<s.size(); ++i){ if (counts[s[i]-'a'] == 1) return i; } return index; } };
上面可以优化,第一遍遍历数组,统计每个字符第一次出现的位置,用一个独有的数字标识重复出现的字符。第二次遍历时只需要遍历新数组即可。
class Solution { public: int firstUniqChar(string s) { vector<int> pos(26, -1); int index; int len = s.size(); for (int i=0; i<len; ++i){ index = s[i]-'a'; if (pos[index] < 0){ pos[index] = i; } else{ pos[index] = len; } } index = len; for (int i=0; i<26; ++i){ if (pos[i] < len && pos[i] > -1) index = min(index, pos[i]); } if (index == len) return -1; return index; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。