【算法笔记】哈希表
2022/1/20 20:13:10
本文主要是介绍【算法笔记】哈希表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
基础知识
-
哈希表定义:哈希表是根据关键码的值而直接进行访问的数据结构。
哈希表就是数组。哈希表中的关键码就是数组的索引下标,然后通过下标直接访问数组中的元素 -
应用场景:一般哈希表都是用来快速判断一个元素是否出现集合里。
例如查询一个名字是否在这所学校里。用哈希表时间复杂度O(1)。 -
哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里。
-
哈希碰撞:两个学生映射的索引一样。
解决方法:
1.拉链法:将发生碰撞的学生存在链表
2.线性探测法:前提哈希表足够大,保证哈希表中还有空位存放发生碰撞的学生。 -
常见的哈希结构 数组、set、map、set的三种结构
unordered_set、set、multiset
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
map的三种结构unordered_map、map、multimap
map 是一个key,value 的数据结构,unordered_map、map、multimap和set的适用场景类似。
例题
242. 有效的字母异位词
分析:字符串中只有小写英文字符,设一个26大小数组,统计字符串中字母的个数,以字母的ascll码作为索引,映射到哈希表中。
遍历s字符串时,对s[i]对应的索引位置做加1;在遍历t时,对t[i]对应的索引位置做减1。最后判断record是不是全为0.
class Solution { public: bool isAnagram(string s, string t) { int record[26]{0};//初始化0 for(int i=0;i<s.length();i++){ record[s[i]-'a']++; } for(int i=0;i<t.length();i++){ record[t[i]-'a']--; } for(int i=0;i<26;i++){ if(record[i]){ return false; } } return true; } };
383. 赎金信
分析:以小写字母作为索引,统计magazine中字符的个数。在遍历ransomNote时,如果record对应的值不为0,做减一;否则返回false。
class Solution { public: bool canConstruct(string ransomNote, string magazine) { int recore[26]{0}; for(int i=0;i<magazine.length();i++){ recore[magazine[i]-'a']++; } for(int i=0;i<ransomNote.length();i++){ if(recore[ransomNote[i]-'a']!=0){ recore[ransomNote[i]-'a']--; } else{ return false; } } return true; } };
49. 字母异位词分组
分析:使用unordered_map
每一组的字符串都是相同字母的不同组合
以strs的字符串按顺序排列作为key,以key的不同组合作为vlaue。
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string> >groups; vector<vector<string> >result; for(int i=0;i<strs.size();i++){ string s=strs[i]; sort(s.begin(),s.end()); groups[s].push_back(strs[i]); } for (auto iter = groups.begin(); iter != groups.end(); ++iter){ result.push_back(iter->second);//只取值value } return result; } };
349. 两个数组的交集
取交集立即想到set,本题对结果顺序没有要求,可以用unordered_set,效率比较快。
unordered_set不允许重复,也就是有去重的功能。先将nums1的内容放在unordered_set,判断nums2是否在unordered_set。
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result_set;//存放结果 unordered_set<int> nums_set(nums1.begin(),nums1.end());//将nums1放num_set中 for(int num:nums2){//遍历nums2,若和nums_set一样,就放在result_set中 if(nums_set.find(num)!=nums_set.end()) result_set.insert(num); } return vector<int>(result_set.begin(),result_set.end()); } };
350. 两个数组的交集 II
上一个题目统计不同数值的并集,也就是结果一定是互不相同的数值
本题的结果可能会出现重复的数值,例如
1 , 2 , 2 , 1
2, 2
本题的并集为2,2
本题考虑用unordered_map,先统计nums1各数值出现的次数,然后遍历nums2是否在umap且umap[num]不为0(若等于0,说明num在nums1出现的次数少,在nums2出现的次数多,取次数少的),若是,则num放在result中,umap[num]- -。
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int> umap;//默认value为0 vector<int> result; for(int num:nums1){ umap[num]++; } for(int num:nums2){ if(umap[num]>0){ result.push_back(num); umap[num]--; } } return result; } };
202. 快乐数
分析:如果是快乐数,最终和会变为1;如果不是快乐数,会出现重复,可以想到set去重的功能。只要和在set中,直接返回false。
class Solution { public: int allSum(int n){ int sum=0; while(n!=0){ sum=sum+(n%10)*(n%10); n=n/10; } return sum; } bool isHappy(int n) { unordered_set<int> uset; int sum=allSum(n); while(uset.find(sum)==uset.end()){//如何可以找到,说明出现重复 if(sum==1){ return true; } uset.insert(sum); sum=allSum(sum); } return false; } };
1. 两数之和
这里用map集合(num[i]为key,i为value),遍历nums,如果target-nums[i]在map中,说明找到了两个之和==target;否则,将i,nums[i]插入map。
emplace()插入键值对
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> umap; vector<int> result; for(int i=0;i<nums.size();i++){ auto it=umap.find(target-nums[i]); if(it!=umap.end()){//找到了符合的键值对 result.push_back(it->second); result.push_back(i); return result; } umap.emplace(nums[i],i); } return result; } };
454. 四数相加 II
设一个unordered_map,以元素之和为key,元素之和出现的次数为value。
统计前两个数组元素之和出现的次数,并放在umap中。
遍历后两个数组,如果后两个数组元素之和的相反数在umap中,就将umap的value加到count。
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int,int> umap; int count=0; for(int a:nums1){//统计nums1+nums2元素和出现次数 for(int b:nums2){ umap[a+b]++; } } for(int c:nums3){ for(int d:nums4){ if(umap.find(0-c-d)!=umap.end()){//判断nums3+nums4是否与nums1+nums2互为相反数 count+=umap[0-c-d]; } } } return count; } };
15. 三数之和
双指针,设两个指针left,right,num[i]表示三元组的第一个元素,num[left]表示三元组的第二个元素,num[right]表示三元组的第三个元素。
先排序
如果num[i]==0,直接结束,后面不会有和为0
如果nums[i]+nums[left]+nums[right]<0,left++;
如果nums[i]+nums[left]+nums[right]>0,right–
如果nums[i]+nums[left]+nums[right]==0,right–,left++,并且要去重
后两个元素去重写在条件内
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int> >result; sort(nums.begin(),nums.end()); int len=nums.size(); for(int i=0;i<len;i++){ if(nums[i]>0){ return result; } if(i>0 && nums[i]==nums[i-1]){//三元组的第一个元素去重 continue; } int left=i+1; int right=len-1; while(left<right){ if(nums[i]+nums[left]+nums[right]>0){ right--; } else if(nums[i]+nums[left]+nums[right]<0){ left++; } else { result.push_back(vector<int>{nums[i],nums[left],nums[right]}); while(right>left && nums[right]==nums[right-1])//三元组的第三个元素去重 right--; while(right>left && nums[left]==nums[left+1])//三元组的第二个元素去重 left++; right--; left++; } } } return result; } };
18. 四数之和
和三数之和差不多,多了一层循环,另外此写法
if (nums[i] > target) { return result; }
不正确,当target是负数时,假设nums[i]>target,如果后面的数是负数,由于负数相加和变小,还可能出现==target的情况
由此五数之和、六数之和都可以这样写出。
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int> >result; sort(nums.begin(),nums.end()); int len=nums.size(); for(int i=0;i<len;i++){//四元组{nums[i],nums[j],nums[left],nums[right]},即为{a,b,c,d} if(i>0 && nums[i]==nums[i-1]){//a去重 continue; } for(int j=i+1;j<len;j++){ if(j>i+1 && nums[j]==nums[j-1]){//b去重 continue; } int left=j+1; int right=len-1; while(right>left){ if(nums[i]+nums[j]>target-(nums[left]+nums[right])){ right--; } else if(nums[i]+nums[j]<target-(nums[left]+nums[right])){ left++; } else{ result.push_back(vector<int> {nums[i],nums[j],nums[left],nums[right]}); while(right>left && nums[left]==nums[left+1])//c去重 left++; while(right>left && nums[right]==nums[right-1])//d去重 right--; left++; right--; } } } } return result; } };
总结
哈希表用于快速判断某个元素是否在集合里
哈希表有三种结构:数组、set、map
- 数组应用的场景:集合的规模不是很大且已经确定,当集合规模很大时,就考虑后面两种结构。
- set应用的场景:集合的规模很大,数据要去重。当不仅要判断元素是否在集合里,还要求记录元素的相关信息,考虑map。
- map应用的场景:map是一种<key, value>的结构,当用于分组,归类时(一个key对应一类),可以考虑map,当数组、set无法解决问题时考虑map。
unordered_set、multiset、set的应用场景(map同理):
- 当题目不要求有序用unordered_set
- 当题目有重复值 用multiset
- 前两个都不合适,则用set
map是万能的哈希表,可以替代数组和set,但是map消耗的空间比较大,在执行效率上不如前两个高效。
这篇关于【算法笔记】哈希表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现