[LeetCode][LCR169]招式拆解 II——巧妙利用字母的固定顺序实现查找复杂度为O(1)的哈希表

题目

LCR 169. 招式拆解 II

某套连招动作记作仅由小写字母组成的序列 arr，其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。

• 示例 1：

输入：arr = "abbccdeff"
输出：a

• 示例 2：

输入：arr = "ccdd"
输出：' '

• 限制：
  0 <= arr.length <= 50000

思考

1. 这道题本身并不难，只需要遍历给出的数据，将所有字母出现次数记录下来
2. 如果是按出现顺序记录的，那么遍历哈希表，直接返回第一个只出现一次的字母即可
3. 如果是记录时是无序的，那么再次遍历 arr 即可
4. 由于 c++ 没有按插入顺序存储的哈希表的数据结构类型，故使用 unorder_map+vector 记录字母出现的顺序
5. 为什么使用 unorder_map 呢？unordered_map 基于哈希表实现，插入和查找元素的平均时间复杂度为 O(1)，但最坏情况下的时间复杂度为 O(n)；而 std::map 是基于红黑树实现的关联容器，用于存储键-值对，并根据键进行排序和查找。对于 std::map ，查找特定键的元素的时间复杂度是 O(log n)，其中n是map中元素的数量。插入键值对的时间复杂度也是 O(log n)。而本题中键本身的顺序并无作用，故只使用平均时间复杂度较小的 unorder_map。
6. 使用哈希表的这两种解法大同小异，并没有什么本质上的差别。但是我们注意到题目中规定只有小写字母，由于小写字母是连续出现的，且个数少而确定，那么我们可以开辟一个含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 ' ';
    }
};
1
2
3
4
5
6
7
8
9
10
11

解法2：利用数组模拟哈希表

class Solution {
public:
    char dismantlingAction(string arr) {
        vector<int> v(26, 0);//大小26个元素，初始化为0
        for(auto &ele:arr) v[ele-'a']++;
        for(auto &ele:arr) if(v[ele-'a']==1) return ele;
        return ' ';
    }
};
1
2
3
4
5
6
7
8
9