网站建设的内容管理,个人信息网站html,wordpress后台背景,辅料企业网站建设费用哈希表理论基础
哈希表是根据关键码的值而直接进行访问的数据结构。
当我们遇到了要快速判断一个元素是否出现集合里的时候#xff0c;就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间#xff0c;因为我们要使用额外的数组#xff0c;set或者是map来存放数据#…哈希表理论基础
哈希表是根据关键码的值而直接进行访问的数据结构。
当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间因为我们要使用额外的数组set或者是map来存放数据才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法 常见的三种哈希结构
当我们想使用哈希法来解决问题的时候我们一般会选择如下三种数据结构。
数组set 集合map(映射)
这里数组就没啥可说的了我们来看一下set。
在C中set 和 map 分别提供以下三种数据结构其底层实现以及优劣如下表所示 std::unordered_set底层实现为哈希表std::set 和std::multiset 的底层实现是红黑树红黑树是一种平衡二叉搜索树所以key值是有序的但key不可以修改改动key值会导致整棵树的错乱所以只能删除和增加。 std::unordered_map 底层实现为哈希表std::map 和std::multimap 的底层实现是红黑树。同理std::map 和std::multimap 的key也是有序的这个问题也经常作为面试题考察对语言容器底层的理解。
当我们要使用集合来解决哈希问题的时候优先使用unordered_set因为它的查询和增删效率是最优的如果需要集合是有序的那么就用set如果要求不仅有序还要有重复数据的话那么就用multiset。
那么再来看一下map 在map 是一个key value 的数据结构map中对key是有限制对value没有限制的因为key的存储方式使用红黑树实现的。
其他语言例如java里的HashMap TreeMap 都是一样的原理。可以灵活贯通。
虽然std::set、std::multiset 的底层实现是红黑树不是哈希表std::set、std::multiset 使用红黑树来索引和存储不过给我们的使用方式还是哈希法的使用方式即key和value。所以使用这些数据结构来解决映射问题的方法我们依然称之为哈希法。 map也是一样的道理。
这里在说一下一些C的经典书籍上 例如STL源码剖析说到了hash_set hash_map这个与unordered_setunordered_map又有什么关系呢
实际上功能都是一样一样的 但是unordered_set在C11的时候被引入标准库了而hash_set并没有所以建议还是使用unordered_set比较好这就好比一个是官方认证的hash_sethash_map 是C11标准之前民间高手自发造的轮子。 242:有效字母的异位词
class Solution {
public:bool isAnagram(string s, string t) {int record[26] {0};for (int i 0; i s.size(); i) {record[s[i] - 97];}for (int i 0; i t.size(); i) {record[t[i] - 97]--;}for (int i 0; i 26; i) {if (record[i] ! 0) {return false;}}return true;}
}; 349:两个数组的交集
使用数组做哈希表
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set; // 存放结果之所以用set是为了给结果集去重int hash[1005] {0}; // 默认数值为0for (int num : nums1) { // nums1中出现的字母在hash数组中做记录hash[num] 1;}for (int num : nums2) { // nums2中出现话result记录if (hash[num] 1) {result_set.insert(num);}}return vectorint(result_set.begin(), result_set.end());}
};
使用unordered_set
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set; // 存放结果之所以用set是为了给结果集去重unordered_setint nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) ! nums_set.end()) {result_set.insert(num);}}return vectorint(result_set.begin(), result_set.end());}
};
202:快乐数
class Solution {
public:int getSum(int n){int sum 0;while(n){sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {unordered_setintset;while(1){int sum getSum(n);if(sum 1){return true;}if(set.find(sum) ! set.end()){return false;}else{set.insert(sum);}n sum;}}
};
1:两数之和
map方法
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,intmap;for(int i 0;inums.size();i){auto tmp map.find(target - nums[i]);if(tmp ! map.end()){return {tmp-second,i};}else{map.insert(pairint, int(nums[i], i));}}return {};}
};
454:四数相加
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint, int umap; //key:ab的数值value:ab数值出现的次数for (int a :nums1) {for (int b : nums2) {umap[a b];}}int count 0; for (int c : nums3) {for (int d : nums4) {if (umap.find(0 - (c d)) ! umap.end()) {count umap[0 - (c d)];}}}return count;}
};
15:三数之和没搞明白有哈希和双指针两种办法下面是双指针法
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[left], c nums[right]for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了if (nums[i] 0) {return result;}// 错误去重a方法将会漏掉-1,-1,2 这种情况/*if (nums[i] nums[i 1]) {continue;}*/// 正确去重a方法if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {// 去重复逻辑如果放在这里000 的情况可能直接导致 rightleft 了从而漏掉了 0,0,0 这种三元组/*while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;*/if (nums[i] nums[left] nums[right] 0) right--;else if (nums[i] nums[left] nums[right] 0) left;else {result.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}return result;}
};
使用数组和set来做哈希法的局限。
数组的大小是受限制的而且如果元素很少而哈希值太大会造成内存空间的浪费。set是一个集合里面放的元素只能是一个key而两数之和这道题目不仅要判断y是否存在而且还要记录y的下标位置因为要返回x 和 y的下标。所以set 也不能用。
map是一种key, value的结构本题可以用key保存数值用value在保存数值所在的下标。所以使用map最为合适。
C提供如下三种map详情请看关于哈希表你该了解这些 (opens new window)
std::mapstd::multimapstd::unordered_map
std::unordered_map 底层实现为哈希std::map 和std::multimap 的底层实现是红黑树。
同理std::map 和std::multimap 的key也是有序的这个问题也经常作为面试题考察对语言容器底层的理解1.两数之和 (opens new window)中并不需要key有序选择std::unordered_map 效率更高
