本文主要是介绍[LeetCode][LCR169]招式拆解 II——巧妙利用字母的固定顺序实现查找复杂度为O(1)的哈希表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
LCR 169. 招式拆解 II
某套连招动作记作仅由小写字母组成的序列 arr，其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。
- 示例 1：
输入：
arr = "abbccdeff"
输出：a
- 示例 2：
输入：
arr = "ccdd"
输出：' '
- 限制：
0 <= arr.length <= 50000
思考
- 这道题本身并不难，只需要遍历给出的数据，将所有字母出现次数记录下来
- 如果是按出现顺序记录的，那么遍历哈希表，直接返回第一个只出现一次的字母即可
- 如果是记录时是无序的，那么再次遍历 arr 即可
- 由于 c++ 没有按插入顺序存储的哈希表的数据结构类型，故使用
unorder_map+vector记录字母出现的顺序 - 为什么使用
unorder_map呢？unordered_map基于哈希表实现，插入和查找元素的平均时间复杂度为 O(1)，但最坏情况下的时间复杂度为 O(n)；而std::map是基于红黑树实现的关联容器，用于存储键-值对，并根据键进行排序和查找。对于std::map，查找特定键的元素的时间复杂度是 O(log n)，其中n是map中元素的数量。插入键值对的时间复杂度也是 O(log n)。而本题中键本身的顺序并无作用，故只使用平均时间复杂度较小的unorder_map。 - 使用哈希表的这两种解法大同小异，并没有什么本质上的差别。但是我们注意到题目中规定只有小写字母，由于小写字母是连续出现的，且个数少而确定，那么我们可以开辟一个含26个元素的数组充当哈希表，从而达到 100% 的时间复杂度为 O(1) 的查找、插入操作，且避免了由哈希表映射操作等带来的额外的时间复杂度
解法1：unorder_map 哈希表
class Solution {
public:char dismantlingAction(string arr) {unordered_map<char, bool> hmap;for(char c : arr)hmap[c] = hmap.find(c) == hmap.end();for(char c : arr)if(hmap[c]) return c;return ' ';}
};
解法2：利用数组模拟哈希表
class Solution {
public:char dismantlingAction(string arr) {vector<int> v(26, 0);//大小26个元素，初始化为0for(auto &ele:arr) v[ele-'a']++;for(auto &ele:arr) if(v[ele-'a']==1) return ele;return ' ';}
};
这篇关于[LeetCode][LCR169]招式拆解 II——巧妙利用字母的固定顺序实现查找复杂度为O(1)的哈希表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
