探索基础算法里的哈希相关构造
目录
- 一，哈希表概览
- 二，算法原理与代码实现
- 1.两数之和
- 349.两数组交集
- 面试题01.02.判断字符重排
- 217.存在重复元素
- 219.存在重复元素II
- 692.前k高频单词
- 45.字母异位词分组
- 三，算法总结
一，哈希表概览
哈希思想是算法中极为关键的思想，体现的是一种映射关系，而哈希表就是依据哈希思想构建的用于存储数据的容器。哈希表的功用在于能快速查找某个元素，其时间复杂度为O(1)，不过遍历整个哈希表的时间复杂度是O(n)。
运用哈希通常有两种途径：
(1) STL中的unordered系列容器。
(2) 用数组模拟简易哈希表。这类情况一般适用于处理字符串中的“字符”或者当数据范围很小时使用。
接下来会通过若干题目深入领会哈希表的运用。
二，算法原理与代码实现
1.两数之和
算法原理：
(1) 要是能预先把数组里的元素和对应的下标关联起来存入哈希表，之后直接在哈希表中查找每个元素对应的target - nums[i]，就能迅速找到目标和的下标。
(2) 这里有个小窍门，不用把所有元素都放进哈希表后再进行二次遍历（因为要处理元素相同的情况）。而是在往哈希表放元素的同时，直接检查表中是否已经存在当前元素所对应的目标元素（即target - nums[i]）。要是存在，那就已经找到对应解，立刻返回。无需把所有元素都放进哈希表，以此提高效率。
(3) 由于哈希表中查找元素的时间复杂度是O(1)，遍历一遍数组的时间复杂度是O(N)，所以能把时间复杂度降到O(N)。
代码实现：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hash; // 存储元素和对应的下标
for(int i = 0; i < nums.size(); i++)
{
// 查看在该元素之前是否存在一个数等于target - nums[i]
int x = target - nums[i];
if(hash.count(x)) return {hash[x], i};
hash[nums[i]] = i; // 不存在就插入
}
return {-1, -1};
}
};
349.两数组交集
算法原理：
解法1：利用哈希表 。
定义两个哈希表hash1和hash2，把两个数组分别放入哈希表进行去重，然后遍历hash1中的每个元素，在hash2中查找是否存在，若存在就是交集。把交集存入数组即可。
代码实现：
class Solution
{
public:
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());
// 遍历s1，在s2中查找是否存在，存在则为交集
vector<int> ret;
for(auto x : s1)
if(s2.find(x) != s2.end())
ret.push_back(x);
return ret;
}
};
解法2：使用set排序+去重。
这种解法不仅能找出交集，还能找到差集。
把两个数组都放进set容器实现排序+去重的效果，接着依次比较两个set里的元素，谁小谁就移动指针，相等时就同时移动指针，此时相等的元素就是交集，较小的元素就是差集，直到其中一个set遍历完，另一个set剩下的元素就是差集。
代码实现：
class Solution
{
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
// 排序+去重
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
// 依次比较，谁小谁移动指针，相等则为交集，然后同时移动指针
auto it1 = s1.begin(), it2 = s2.begin();
vector<int> ret;
while (it1 != s1.end() && it2 != s2.end())
{
if (*it1 < *it2) ++it1;
else if (*it1 > *it2) ++it2;
else ret.push_back(*it1), ++it1, ++it2;
}
return ret;
}
};
面试题01.02.判断字符重排
算法原理：
(1) 当两个字符串长度不一样时，肯定不能构成互相重排，直接返回false。
(2) 要是两个字符串能构成互相重排，那么每个字符串中各个字符出现的次数必然相同。所以，可以用哈希表分别统计两个字符串中各个字符出现的次数，然后逐个比较是否相等。
代码实现：
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
// 长度不同，直接返回false
if(s1.size() != s2.size()) return false;
int hash1[26] = {0}, hash2[26] = {0};
// 先统计s1和s2中每个字符出现的次数
for(auto ch : s1) hash1[ch - 'a']++;
for(auto ch : s2) hash2[ch - 'a']++;
// 再比较两个哈希表中每个字符出现的次数是否相同
for(char ch = 'a'; ch <= 'z'; ch++)
if(hash1[ch - 'a'] != hash2[ch - 'a'])
return false;
return true;
}
};
优化： 只用一个哈希表。
先用一个哈希表统计s1中每个字符出现的个数，然后遍历s2时把s2中出现的字符在哈希表中减1。要是构成重排列，最后哈希表中的个数都为0，否则不构成
。
代码实现：
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
// 长度不同，直接返回false
if(s1.size() != s2.size()) return false;
int hash[26] = {0};
// 统计s1中字符出现的次数
for(auto ch : s1) hash[ch - 'a']++;
// 遍历s2，出现的字符减1
for(auto ch : s2) hash[ch - 'a']--;
// 最后检查hash里是否都为0
for(int i = 0; i < 26; i++)
if(hash[i] != 0)
return false;
return true;
}
};
217.存在重复元素
算法原理：
这道题和第一题做法基本类似。
分析题目，出现至少两次意味着数组中有重复元素，所以无需统计元素出现的数目。只需在遍历数组时，检查当前元素之前是否出现过即可
。
因此可以用哈希表，只存储数组内的元素。遍历数组时，一边检查哈希表中是否已存在当前元素，一边把元素加入哈希表。
代码实现：
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash;
for(auto x : nums)
if(hash.count(x)) return true;
else hash.insert(x);
return false;
}
};
219.存在重复元素II
算法原理：
这道题和上一题大体相同，不过除了要求两个元素相等外，还得判断相等元素的下标差的绝对值是否小于等于k。所以本题的哈希表要把元素值和对应下标绑定
。
细节问题：
要是数组内有大量重复元素，当判断下标差的绝对值不符合要求时，插入相同元素的下标会覆盖原来的下标，这样结果还对吗，怎么处理？
结果依然正确，可以放心覆盖!
原因：
我们按下标从小到大的顺序遍历数组，当遇到两个相同元素并比较下标时，这两个下标肯定是距离最近的，因为：
(1) 如果当前判断符合条件就直接返回true，不用继续往后查找。
(2)
如果不符合条件，那么前一个下标肯定不可能和后续相同元素的下标匹配（因为下标在逐渐增大），所以可以大胆舍弃前一个存储的下标，换成新的下标，继续匹配
。
代码实现：
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash; // 绑定元素和下标
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]))
{
if(abs(hash[nums[i]] - i) <= k)
return true;
}
hash[nums[i]] = i;
}
return false;
}
};
692.前k高频单词
算法原理：
解法：使用map + 稳定排序函数 。
先用map统计每个单词出现的次数，map中是按单词的字典序排序的，所以还需要用排序函数对次数进行降序排列，最后提取前k个出现最多的字符串。
魔鬼细节问题：
对次数排序时有以下几个注意点：
(1) 排序函数一定要用稳定排序! 算法库中的sort是不稳定的，而stable_sort是稳定的。
因为要是用不稳定的排序，出现次数相同的字符串顺序又会被打乱（map中已经按单词字典序排序），不符合题意 。
(2) 使用排序函数前要把map中的元素先导入vector中，再把vector的迭代器传给stable_sort 。
因为stable_sort只能传随机迭代器，而map的迭代器是双向迭代器，vector的迭代器是随机迭代器。
(3) stable_sort的第三个参数：一个可调用的比较函数和函数对象。
代码实现：
class Solution
{
struct kvcmp
{
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
{
return kv1.second > kv2.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k)
{
// 统计每个字符串出现的次数
map<string, int> mapCnt;
for(auto& s : words) mapCnt[s]++;
vector<pair<string, int>> v(mapCnt.begin(), mapCnt.end());
// 用稳定排序对字符串出现的次数降序排列
stable_sort(v.begin(), v.end(), kvcmp());
// 提取前k个出现次数最多的单词
vector<string> ret;
for(int i = 0; i < k; i++)
ret.push_back(v[i].first);
return ret;
}
};
45.字母异位词分组
算法原理：
这道题要解决两个问题：
**(1) 判断两个字符串是否是字母异位词。可以用上面题目的方法用哈希表统计字符出现的个数来判断。这里用更简洁的方法，排序，不过时间复杂度更高。把每个字符串按字典序排序，若是字母异位词，排序后字符串相等，否则不相等。
(2) 如何把字母异位词分组。
可以这样定义哈希表，把key定义为string，把value定义为字符串数组vector< string >。
把每个字符串排序后在哈希表中查找，如果存在，就把它放到对应的字符串数组中** 。
代码实现：
```cpp
class Solution
{
public:
vector
{
unordered_map
// 把所有字母异位词分组
for(auto& s : strs)
{
string tmp = s;
sort(tmp.begin(), tmp.end());
hash[tmp].push_back(s);
}
// 提取结果
vector<vector<string>> ret;
for(auto& [x, y] : hash)
ret.push_back(y);
return
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/12765.html
