哈希表理论基础;242.有效的字母异位词349. 两个数组的交集202. 快乐数1. 两数之和
6.2 哈希冲突 - Hello 算法 (hello-algo.com)
1哈希表理论基础
又称散列表
一般哈希表都是用来快速判断一个元素是否出现集合里。
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法
1.1哈希函数
- 通过某种哈希算法
hash()
计算得到哈希值。 - 将哈希值对桶数量(数组长度)
capacity
取模,从而获取该key
对应的数组索引index
。
1.2哈希碰撞
2个输入元素都索引到了相同的输出位置,称为哈希碰撞
解决方法
- 扩容哈希表
「负载因子 load factor」是哈希表的一个重要概念,其定义为哈希表的元素数量除以桶数量,用于衡量哈希冲突的严重程度,也常作为哈希表扩容的触发条件。
- 改良哈希表数据结构,使得哈希表可以在出现哈希冲突时正常工作。
- 仅在必要时,即当哈希冲突比较严重时,才执行扩容操作。
1.2.1 链式地址
1.2.2 开放寻址
1. 线性探测
2. 平方探测
平方探测与线性探测类似,都是开放寻址的常见策略之一。当发生冲突时,平方探测不是简单地跳过一个固定的步数,而是跳过“探测次数的平方”的步数,即 1,4,9,… 步。
3. 多次哈希
顾名思义,多次哈希方法使用多个哈希函数f1(x)、f2(x)… 进行探测。
1.3 三种哈希算法的数据结构
1.3.1 数组
1.3.2 set(集合)
集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
1.3.3 map(映射)
映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。
2 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
2.1 思路
暴力法:2层for循环
数组哈希表法:以空间换时间,定义一个26大小的数组,记录在字符串s中出现的字母次数,在字符串t中做减法,如果数组全为空,就说明是字母异位词。(包含完全相同的情况)
2.2 代码
/**
* @file hash_2.h
* @author nrt ([email protected])
* @brief 有效的字母异位词
* @version 0.1
* @date 2023-12-04
*
* @copyright Copyright (c) 2023
*
*/
#include <iostream>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t){
int A[26] = {0};
//字符串s计字符出现次数。做加法
for(int i =0; i < s.size(); i++){
A[s[i] - 'a'] ++;
}
//字符串t计字符出现次数,做减法
for(int j = 0; j < t.size(); j++){
A[t[j] - 'a'] --;
}
//不为零,就说明有字符不同
for(int x = 0; x < 26 ; x++){
if(A[x] != 0){
return false;
}
return true;
}
}
};
3 两个数组的交集
给定两个数组,编写一个函数来计算它们的交集。
3.1 思路
主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。
3.2 unordered_set
无序集合(unordered_set)是一种使用哈希表实现的无序关联容器,其中键被哈希到哈希表的索引位置,因此插入操作总是随机的。
无序集合上的所有操作在平均情况下都具有常数时间复杂度O(1),但在最坏情况下,时间复杂度可以达到线性时间O(n),这取决于内部使用的哈希函数,但实际上它们表现非常出色,通常提供常数时间的查找操作。
3.3 代码
/**
* @file hash_3.h
* @author nrt ([email protected])
* @brief 3 两个数组的交集
* 给定两个数组,编写一个函数来计算它们的交集。
* 学会使用一种哈希数据结构:unordered_set
* @version 0.1
* @date 2023-12-04
*
* @copyright Copyright (c) 2023
*
*/
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution{
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
//数组1的头到尾
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for(int num : nums2){
if(nums_set.find(num) != nums_set.end()){
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
4.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
4.1 思路
判断sum是否重复出现就可以使用unordered_set。
这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。
4.2 代码
/**
* @file hash_4.h
* @author nrt ([email protected])
* @brief 快乐数
* @version 0.1
* @date 2023-12-04
*
* @copyright Copyright (c) 2023
*
*/
#include<iostream>
#include<unordered_set>
using namespace std;
class Solution {
public:
// 取数值各个位上的单数之和
int getSum(int n){
int sum = 0;
while (n)
{
sum = (n%10) * (n%10);
n = n/10;
}
}
bool isHappy(int n) {
unordered_set<int> result_set;
while(1){
int sum = getSum(n);
if(sum == 1){
return true;
}
if (result_set.find(sum) != result_set.end()) {
return false;
} else {
result_set.insert(sum);
}
n = sum;
}
}
};
5. 两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
5.1 思路
本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适。
5.2 unordered_map
C++总结(7):STL无序容器之unordered_set、unordered_map、unordered_multiset、unordered_multimap详解-CSDN博客
5.3 代码
/**
* @file hash_5.h
* @author nrt ([email protected])
* @brief 两数之和
* @version 0.1
* @date 2023-12-04
*
* @copyright Copyright (c) 2023
*
*/
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
auto iter = map.find(target - nums[i]);
if(iter != map.end()){
return {iter->second, i};//iter->second
}
map.insert(pair<int,int>(nums[i], i));//pair
}
return {};
}
};
总结:
需要学习C++的STL。对STL无序容器之unordered_set、unordered_map不熟悉。
代码复现不熟练。
标签:std,map,set,key,代码,day5,随想录,哈希,unordered From: https://www.cnblogs.com/nrtnrt/p/17874555.html