剑指 Offer 50. 第一个只出现一次的字符(C++) 有序哈希表

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"
s = "" 
返回 " "

限制:

0 <= s 的长度 <= 50000

有序哈希表

在哈希表的基础上,有序哈希表中的键值对是 按照插入顺序排序 的。基于此,可通过遍历有序哈希表,实现搜索首个 “数量为 1 的字符”。

哈希表是 去重 的,即哈希表中键值对数量 ≤ 字符串 s 的长度。因此,相比哈希表方法,减少了第二轮遍历的循环次数。当字符串很长(重复字符很多)时,本方法则效率更高。

复杂度分析:

时间复杂度 O(N) : N 为字符串 s 的长度;需遍历 s 两轮,使用 O(N);vector 查找操作的复杂度为 O(1) ;
空间复杂度 O(1) : 由于题目指出 s 只包含小写字母,因此最多有 26 个不同字符,vector 存储需占用 O(26) = O(1)的额外空间。

由于 C++ 未提供自带的链式哈希表,因此借助一个 vector 按序存储哈希表 dic 中的 key ,第二轮遍历此 vector 即可。

剑指 Offer 50. 第一个只出现一次的字符(C++)   有序哈希表
剑指 Offer 50. 第一个只出现一次的字符(C++)   有序哈希表
剑指 Offer 50. 第一个只出现一次的字符(C++)   有序哈希表
剑指 Offer 50. 第一个只出现一次的字符(C++)   有序哈希表

剑指 Offer 50. 第一个只出现一次的字符(C++)   有序哈希表

class Solution {
public:
    char firstUniqChar(string s) {
        vector<char> keys;//存放字母的数组
        unordered_map<char, bool> dic;//存放判断的哈希表
        for(char c : s) {
            if(dic.find(c) == dic.end())//若C不存在于dic里面
            //则,加进来keys
                keys.push_back(c);
            dic[c] = dic.find(c) == dic.end();//若dic.find(c) == dic.end()成立,
            //则dic[c] = true;若C已经在前面出现过,C就是出现在dic;
            //因此,则dic[c] = false
        }
        for(char c : keys) {
            if(dic[c]) return c;
        }
        return ' ';
    }
};

作者:jyd
链接:https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

上一篇:【jmespath】—2. 进阶 List and Slice Projections


下一篇:剑指 Offer 50. 第一个只出现一次的字符