算法与数据结构基础 - 哈希表(Hash Table)
Hash Table基础
哈希表(Hash Table)是常用的数据结构,其运用哈希函数(hash function)实现映射,内部使用开放定址、拉链法等方式解决哈希冲突,使得读写时间复杂度平均为O(1)。
HashMap(std::unordered_map)、HashSet(std::unordered_set)的原理与Hash Table一样,它们的用途广泛、用法灵活,接下来侧重于介绍它们的应用。
相关LeetCode题:
集合
如果仅需要判断元素是否存在于某个集合,我们可以使用结构HashSet(std::unordered_set)。例如 LeetCode题目 349. Intersection of Two Arrays:
// 349. Intersection of Two Arrays
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s1(nums1.begin(),nums1.end());
unordered_set<int> s2(nums2.begin(),nums2.end());
vector<int> res;
for(auto& a:s1)
if(s2.count(a)) res.push_back(a);
return res;
}
相关LeetCode题:
349. Intersection of Two Arrays 题解
720. Longest Word in Dictionary 题解
计数
如果需要对元素进行计数,我们可以使用结构HashMap(std::unordered_map),元素如取值范围固定可以用Array(std::vector),例如LeetCode题目 217. Contains Duplicate:
// 217. Contains Duplicate
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> m;
for(int x:nums) if(m[x]++==) return true;
return false;
}
相关LeetCode题:
266. Palindrome Permutation 题解
748. Shortest Completing Word 题解
451. Sort Characters By Frequency 题解
30. Substring with Concatenation of All Words 题解
在滑动窗口算法中常使用HashMap计数,关于滑动窗口算法,详见:算法与数据结构基础 - 滑动窗口(Sliding Window)
Key-Val
进一步地,HashMap表示一种Key-Val (或ID-属性) 关系,这里Val可以是计数、下标(index)等等。
相关LeetCode题:
953. Verifying an Alien Dictionary 题解
981. Time Based Key-Value Store 题解
244. Shortest Word Distance II 题解
映射
更一般地,HashMap表示一种映射关系,意义在于O(1)时间复杂度完成由 A->B 的映射。
相关LeetCode题:
535. Encode and Decode TinyURL 题解
HashMap与Prefix sum
利用HashMap和Prefix sum,我们可以在O(n)时间复杂度求解一类子序列求和问题,其中HashMap用于计数,例如LeetCode题目 560. Subarray Sum Equals K:
// 560. Subarray Sum Equals K
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> m;
m[]=;
int sum=,res=;
for(auto& a:nums){
sum+=a;
res+=m[sum-k];
m[sum]++;
}
return res;
}
相关LeetCode题:
930. Binary Subarrays With Sum 题解
325. Maximum Size Subarray Sum Equals k 题解
HashMap与图形问题
HashMap可以应用于二维图形的一些问题求解,以欧拉距离、斜率、x/y坐标等为key,以计数、x/y坐标为val。图形问题中HashMap的映射关系不是那么直观和明显,需要单独计算key、仔细甄别映射关系。
相关LeetCode题:
939. Minimum Area Rectangle 题解
HashMap与vector/list/stack结合
HashMap与vector、list、stack等数据结构可以结合成为复合数据结构,这样可以既用到HashMap O(1)的优点,也用到vector支持下标操作、list增删节点快、stack先进后出的特点。例如 LeetCode题目 380. Insert Delete GetRandom O(1):
// 380. Insert Delete GetRandom O(1)
vector<int> v;
unordered_map<int,int> m;
以上用vector存储元素,unordered_map存储元素和对应下标;getRandom函数利用vector下标操作,而删除元素时,使用unordered_map取得被删元素、将vector末尾元素与其对调,利用了HashMap O(1)的优点。
相关LeetCode题:
380. Insert Delete GetRandom O(1) 题解
895. Maximum Frequency Stack 题解
最新文章
- Node学习笔记(四):gulp+express+io.socket部署angularJs2(填坑篇)
- HBase查找一条数据的过程
- 如何用Matlab将cell数据写入文件
- 自己留存:小经验在asp.net 4.5或者asp.net mvc 5解决A potentially dangerous Request.Form value was detected from the client
- Vmware9.0打开早期版本报错:this virtual machine’s policies are too old to be run by this version of vmware workstation”
- josephus Problem 中级(使用数组模拟链表,提升效率)
- 实习小记-python中不可哈希对象设置为可哈希对象
- PHP之路——Mysql多表查询
- 02、Unicode 汉子转码小工具
- 智能家居DIY
- javaWEB总结(12):JSP页面的九个隐含对象
- Linux下的Locale详解
- 2018-2019-2 20165328《网络对抗技术》Exp0 Kali安装week1
- Java多线程之synchronized及其优化
- 【二维树状数组】计数问题 @JSOI2009/upcexam5911
- VLAN 及 GVRP 配置
- 【Algorithm】选择排序
- Unity学习笔记(3):一些常用API和应用场景
- 关于OpenLDAPAdmin管理页面提示“This base cannot be created with PLA“问题. Strong Authentication Required问题
- js获取checkbox值的方法
热门文章
- Python操作ElasticSearch
- TCP/IP 第三章
- centOS7.3 6忘记密码/修改root密码
- spark入门(四)日志配置
- 【深入浅出-JVM】(34):CMS 回收器
- c++学习书籍推荐《C++语言的设计与演化》下载
- Elasticsearch(三) 插件安装
- .Net Core 使用Http请求及基于 Polly 的处理故障
- Spring Boot微服务电商项目开发实战 --- 基础配置及搭建
- InstantiationException:mybatis.spring.transaction.SpringManagedTransactionFactory