专注 效率 记忆
预习 笔记 复习 做题
欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录)
文章字体风格:
红色文字表示:重难点★✔
蓝色文字表示:思路以及想法★✔
如果大家觉得有帮助的话,感谢大家帮忙
点赞!收藏!转发!
本博客带大家一起学习,我们不图快,只求稳扎稳打。
由于我高三是在家自学的,经验教训告诉我,学习一定要长期积累,并且复习,所以我推出此系列。
只求每天坚持40分钟,一周学5天,复习2天
也就是一周学10道题
60天后我们就可以学完81道题,相信60天后,我们一定可以有扎实的代码基础!我们每天就40分钟,和我一起坚持下去吧!
qq群:878080619
十、哈希表
1. 模拟散列表
开散列方法(拉链法)
就记住有N个链表头节点
对于原数据可以 (x % N + N) % N;找到合适位置插入到头节点
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 3; // 取大于1e5的第一个质数,取质数冲突的概率最小 可以百度
//* 开一个槽 h
int h[N], e[N], ne[N], idx; //邻接表
void insert(int x) {
// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x) {
//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if (e[i] == x) {
return true;
}
}
return false;
}
int n;
int main() {
cin >> n;
memset(h, -1, sizeof h); //将槽先清空 空指针一般用 -1 来表示
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
insert(x);
} else {
if (find(x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
开放寻址法代码
本质:(最多存1e5个数)
#include <cstring>
#include <iostream>
using namespace std;
//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3; //大于数据范围的第一个质数
const int null = 0x3f3f3f3f; //规定空指针为 null 0x3f3f3f3f
int h[N];
int find(int x) {
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x) {
t++;
if (t == N) {
t = 0;
}
}
return t; //如果这个位置是空的, 则返回的是他应该存储的位置
}
int n;
int main() {
cin >> n;
memset(h, 0x3f, sizeof h); //规定空指针为 0x3f3f3f3f
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
h[find(x)] = x;
} else {
if (h[find(x)] == null) {
puts("No");
} else {
puts("Yes");
}
}
}
return 0;
}
2. 未出现过的最小正整数( 2018年全国硕士研究生招生考试 )
由于我们需要从1去找 是否出现在数组中
如果1去遍历一遍数组
2遍历一遍数组
太麻烦
如何一步到位?
其实可以用
哈希思想
把数组出现的数都映射存储到数组中
如何都没有出现文章来源:https://www.toymoban.com/news/detail-544412.html
那么一定是大于数组的个数+1的那个值文章来源地址https://www.toymoban.com/news/detail-544412.html
class Solution {
public:
int findMissMin(vector<int>& nums) {
int n = nums.size();
vector<bool> hash(n + 1);
for (int x: nums)
if (x >= 1 && x <= n)
hash[x] = true;
for (int i = 1; i <= n; i ++ )
if (!hash[i])
return i;
return n + 1;
}
};
到了这里,关于【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!