题目

题解

三个方法，前两个都是基于哈希表，只是哈希表的实现方式不同；最后一个是对于数据流的处理情况，这个情况只能遍历字符串一遍，因此需要再遍历新定义的哈希表（即vector）一遍。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$

1. 哈希表

class Solution {
public:
    char firstUniqChar(string s) {//三个方法。1.哈希表
        unordered_map<char, int> m;//定义哈希表
        for(auto &c : s) m[c]++;//第一次遍历，确定每个字符的出现次数
        for(auto &c : s){
            if(m[c]==1) return c;//第二次遍历，碰到个数为1的直接返回
        }
        return ' ';//其他情况直接返回空字符
    }
};

2. 自制哈希表

class Solution {//三个方法。2.自制哈希表
public:
    char firstUniqChar(string s) {
        vector<int> m(128,0);//定义自制哈希表，用vector实现
        for(auto &c : s) m[c]++;//第一次遍历，确定每个字符的出现次数
        for(auto &c : s){
            if(m[c]==1) return c;//第二次遍历，碰到个数为1的直接返回
        }
        return ' ';//其他情况直接返回空字符
    }
};

3. 数据流处理

class Solution {//三个方法。3.数据流处理
public:
    char firstUniqChar(string s) {
        vector<int> m(128,-1);//定义自制哈希表，用vector实现
        //只遍历一遍s
        for(int i=0; i<s.size(); ++i){
            //若个数超过1个，标记为-2
            //若个数等于1个，标记为出现的位置
            //其他的都为-1
            if(m[s[i]]==-2) continue;//
            else if(m[s[i]]>=0) m[s[i]]=-2;
            else m[s[i]] = i;  
        }
        //再遍历vector，取出其中不为负且值最小的字符下标
        int res = INT_MAX;
        for(auto &t : m){
            if(t>=0) res = min(res, t);
        }
        //若该下标为INT_MAX说明没有只出现一次的字符，返回空字符
        return res==INT_MAX? ' ':s[res];
    }
};