前言:今天Leetcode遇到一道题很有意思,方法还是老方法,但是得换个新数据结构才能以很简单的算法AC,这就涉及到多个基础数据结构的组合,本节主要回顾一下哈希表和哈希集合在力扣中的基础用法
文章目录
使用场景及概述
当你想通过非遍历或非穷举的方式,快速判断一个元素是否出现集合里,Hash Table是非常合适的数据结构
这里先总述映射和集合的性质
映射 | 底层实现 | 是否有序 | 映射关系 | 增删改查复杂度 |
---|---|---|---|---|
map |
红黑树 | 按key升序 | 一对一 | O ( log n ) O(\log n) O(logn) |
multimap |
红黑树 | 按key升序 | 一对多 |
O ( log n ) O(\log n) O(logn) |
unordered_map |
哈希表 | 乱序 |
一对一 | O(1) |
集合 | 底层实现 | 是否有序 | 元素是否唯一 | 增删改查复杂度 |
---|---|---|---|---|
set |
红黑树 | 升序 | 唯一 | O ( log n ) O(\log n) O(logn) |
multiset |
红黑树 | 升序 | 可重复 |
O ( log n ) O(\log n) O(logn) |
unordered_set |
哈希表 | 乱序 |
唯一 | O(1) |
1 映射容器
其中map
和multimap
的头文件都是
#include <map>
而unordered_map
的头文件是
#include <unordered_map>
1.1 map
map
容器的底层实现是红黑树,且元素按key
值升序排列。因此可保证乱序插入,按key
升序输出,相当于自带sort
buff,用起来实在方便。
map<string, int> map;
map["B"] = 22;
map["A"] = 11;
map["D"] = 44;
map["C"] = 33;
cout << "map中的key值遍历(升序——底层红黑树实现):" << endl;
for (auto& m : map)
cout << m.first << ',' << m.second << endl;
cout << "map中的key值反向迭代器遍历(降序——底层红黑树实现):" << endl;
for (auto it = map.rbegin(); it != map.rend(); it++)
cout << it->first << ',' << it->second << endl;
1.2 multimap
multimap
容器的底层实现也是红黑树,特点是可以实现一对多映射,且元素按key
值升序排列。因此也可保证乱序插入,按key
升序输出。不过插入用法如下
【插入用法】multimap_name.insert({key, element})
multimap<string, int> multiMap;
cout << "multimap中的key值遍历(升序红黑树实现):" << endl;
multiMap.insert({"B", 22});
multiMap.insert({"B", 11});
multiMap.insert({"A", 11});
multiMap.insert({"D", 44});
multiMap.insert({"C", 33});
for (auto& m : multiMap)
cout << m.first << ',' << m.second << endl;
cout << "multimap中的key值反向迭代器遍历(降序——底层红黑树实现):" << endl;
for (auto it = multiMap.rbegin(); it != multiMap.rend(); it++)
cout << it->first << ',' << it->second << endl;
从输出结果看出,multimap
虽然按key
值升序排列,但对于相同key
的不同value
是服从先到先得顺序
1.3 unordered_map
unordered_map
容器的底层实现是Hash Table,元素乱序存储,但增删改查效率极高,复杂度均为
O
(
1
)
O(1)
O(1)
unordered_map<string, int> unMap;
cout << "unordered_map中的key值无序(底层哈希表实现):" << endl;
unMap["B"] = 22;
unMap["A"] = 11;
unMap["D"] = 44;
unMap["C"] = 33;
for (auto& m : unMap)
cout << m.first << ',' << m.second << endl;