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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指 Offer 50. 第一个只出现一次的字符(C++) 有序哈希表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1484字，纯文字阅读大概需要3分钟。

内容图文

在字符串 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 即可。

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

内容总结

以上是互联网集市为您收集整理的剑指 Offer 50. 第一个只出现一次的字符(C++) 有序哈希表全部内容，希望文章能够帮你解决剑指 Offer 50. 第一个只出现一次的字符(C++) 有序哈希表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端