描述

这是一篇针对初学者的题解。共用两种方法解决。
知识点：哈希，bitset
难度：一星

题解

方法一：哈希法

很显然，遍历一遍字符串，统计每个字符出现的次数。然后再遍历一遍字符串，找出答案。

代码一：用map实现

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char, int> mp;
        for (const char ch : str) {
            ++mp[ch];
        }     
        for (int i=0; i<str.length(); ++i) {
            if (mp[str[i]] == 1) return i;
        }
        return -1;
    }
};

代码二：用数组代替map

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int mp[128] = {0};
        for (const char ch : str) {
            ++mp[ch];
        }     
        for (int i=0; i<str.length(); ++i) {
            if (mp[str[i]] == 1) return i;
        }
        return -1;
    }
};

时间复杂度：O(2n), 需要遍历两次字符串
空间复杂度：O(n)

方法二：使用bitset

其实思想还是哈希，主要是这里bitset更节省空间，每个位置的值为0或1， 同时可以练习下bitset的使用。
具体过程：

1. 初始化：bitset<128> b1表示只出现1次， b2表示出现2次以上
2. 遍历字符串，第一次出现，b1[ch] = 1
3. 如果第二次出现，b2[ch] = 1
4. 最后，找出第一个b1[ch] == 1 && b2[ch] == 0的字符

   代码

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        bitset<128> b1, b2;
        for (const char ch : str) {
            if (!b1[ch] && !b2[ch]) {
                b1[ch] = 1;
            }
            else if (b1[ch] && !b2[ch]) {
                b2[ch] = 1;
            }
        }
        for (int i=0; i<str.length(); ++i) {
            if (b1[str[i]] && !b2[str[i]]) {
                return i;
            }
        }
        return -1;
    }
};

时间复杂度：O(2n), 需要遍历两次字符串
空间复杂度：O(n)