题解 | #第一个只出现一次的字符#

第一个只出现一次的字符

http://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c

思路

题目分析

题目给出了我们一个字符串
我们要在字符串中找到第一次只出现一次的字符，返回其下标位置

方法一：枚举
- 我们根据ASCII码知道计算机一共定义了128个字符
- 因此我们只要给出一个空间大于128就可以统计所有字符的个数
- 然后再按照str的字符顺序遍历，查找到第一个数量为1的字符，返回下标
方法二：哈希
- 我们可以通过申请一个哈希表来存储<字符，数量>对
- 统计每个字符出现的数量存储在哈希表内
- 最终顺序遍历str，找到第一个数量为1的字符并返回下标

方法一：枚举

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int count[128] = {0};					// 申请128大小的空间
        for(char c : str) count[c]++;			// 数出str中各个字符的数量
        for(int i = 0; i < str.size(); i++) {
            if(count[str[i]] == 1) return i;	// 顺序遍历str判断其中是否有第一次出现数量为1的字符并返回下标
        }
        return -1;								// 找不到则返回-1
    }
};

复杂度分析

时间复杂度： $O (N)$ ，单轮循环的时间规模
空间复杂度： $O (1)$ ，空间固定大小为128

方法二：哈希

alt

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char, int> m;
        for(char c : str) m[c]++;					// 数出str中各个字符的数量
        for(int i = 0; i < str.size(); i++) {
            if(m[str[i]] == 1) return i;			// 顺序遍历str判断其中是否有第一次出现数量为1的字符并返回下标
        }
        return -1;									// 找不到则返回-1
    }
};

复杂度分析

时间复杂度： $O (N)$ ，单轮循环的时间规模
空间复杂度： $O (1)$ ，如果字符串非常短则空间复杂度和字符串长度字符种类有关，如果字符串很长则取决于ASCII表示的字符种类有限，因此我们统一按 $O (1)$ 规模来看

方法三：哈希+最终遍历优化

我们可以引入一个结构在顺序遍历字符串的时候保留其字符先后出现的信息
这样在找第一个出现次数为1的字符的时候可以通过找顺序出现的字符即可，优化掉对整个字符串的遍历时间

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<int, int> m;                    // 记录字母出现的位置 <字母，索引>
        unordered_map<int, int> seq;                  // 按照出现的顺序记录字母 <顺序，字母>
        int j = 1;                                    // 字母顺序
        for(int i = 0; i < str.size(); i++) {         // 遍历字符串，记录字母出现位置和顺序
            char c = str[i];
            if(!m[c]) {                               // 如果未出现过该字符
                m[c] = i+1;                           // 记录该字符的位置索引+1，+1是为了避开0的出现
                seq[j++] = c;                         // 记录该字符出现的顺序
            }
            else m[c] = -1;                           // 如果出现过该字符则将其位置索引设置为无效值-1
        }
        for(int i = 1; i <= j; i++) if(m[seq[i]] != -1) return m[seq[i]] - 1;    // 直接访问顺序列表找到顺序优先的只出现一次的字符的位置，减1才是最终位置
        return -1;									// 找不到则返回-1
    }
};