Problem: Given a string, find the first non-repeating character in it and return it‘s index. If it doesn‘t exist, return -1.
Example:
s = "leetcode" return 0. s = "loveleetcode", return 2.
本题的第一想法是开一个字母表计数器,遍历string s中的元素，并利用计数器对每一个字母计数。最后再次遍历s，查找计数为1的字符然后返回其索引。该解法代码如下：
1 class Solution { 2 public: 3 int firstUniqChar(string s) { 4 int *alphabet = NULL; 5 alphabet = new int[26](); 6 for(int i = 0; i < s.length(); i++) 7 { 8 alphabet[int(s[i] - ‘a‘)]++; 9 } 10 for(int i = 0; i < s.length(); i++) 11 { 12 if(alphabet[int(s[i] - ‘a‘)] == 1) 13 { 14 return i; 15 } 16 } 17 return -1; 18 19 20 } 21 };
但是，若string非常长，两次遍历则会带来很大的开销，因此，可以考虑一次遍历，用hash table记录每个字母的次数和索引，其代码如下：
1 class Solution { 2 public: 3 int firstUniqChar(string s) { 4 unordered_map<char, pair<int,int>> m; 5 int idx = s.length(); 6 for(int i = 0; i < s.length(); i++) 7 { 8 m[s[i]].first++; 9 m[s[i]].second = i; 10 } 11 for(auto &p:m) 12 { 13 if(p.second.first == 1) 14 { 15 idx = min(idx, p.second.second); 16 } 17 } 18 return idx == s.length()? -1 : idx; 19 } 20 };
LeetCode 387. First Unique Character in a String
原文：http://www.cnblogs.com/yrwang/p/6228090.html