qiaoxu123
2/24/2019 - 12:55 AM

387. First Unique Character in a String

一道非常简单的字符串搜索题目，使用hash方法最简单，但是用的很不熟练。。

  • Approach 1 : hash

  • Approach 2 : pair

if the string is extremely long, we wouldn't want to traverse it twice, so instead only storing just counts of a char, we also store the index, and then traverse the hash table.

就实际来讲，性能上没有丝毫提升，仅仅理论层面上分析

hash.cpp
content_copyfile_download
//Runtime: 64 ms, faster than 44.53%
//Memory Usage: 13.5 MB, less than 49.72%

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> set;
        
        
        for(int i = 0;i < s.length();++i)
            set[s[i]]++;
        
        for(int i = 0;i < s.length();++i){
            if(set[s[i]] == 1)
                return i;
        }
        return -1;
    }
};
test1.cpp
content_copyfile_download
//Runtime: 72 ms, faster than 31.78%
//Memory Usage: 13.7 MB, less than 26.44%

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, pair<int, int>> m;
        int idx = s.size();
        for (int i = 0; i < s.size(); i++) {
            m[s[i]].first++;
            m[s[i]].second = i;
        }
        for (auto &p : m) {
            if (p.second.first == 1) idx = min(idx, p.second.second);
        }
        return idx == s.size() ? -1 : idx;
    }
};