新手光能
我在做题时，想到了一种O(1)的查找法（不能查找数组）
定义一个map,设置为<查找的类型,int>
然后输入要在里面查找的数组时，用map记录下来
随后每一次查找，输出map中的要查找的值
举个例子
#include<iostream>
#include<map>
using namespace std;
map<int,int> t;
int n,a;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
t[a]=i;
}
int m;
cin>>m;
for(int i=1;i<=m;i++){
int tmp;
cin>>tmp;
cout<<t[tmp]<<endl;
}
}
输入数组长度和n个数，
然后输入m,有m次询问
每次输入一个数，输出他的位置（找不到输出0，当然题目要求输出其他的，也可以，特判一下）
输入
5
1 2 3 9 8
4
2 3 9 4
输出
2
3
4
0
甚至比二分还快
时间转空间
李承耀在2022-10-31 20:58:33追加了内容
这里的不能查找数组，是指查找的对象是数组
李承耀在2022-10-31 20:59:34追加了内容
就是你不能在二维数组里面查找一维数组
新手天翼
哈希表是个好玩意儿
哈希表：对于n个对{key,value}，value可以相同，而key必须不同（查找可以省略value）把它们以接近O（1）的时间放入该表后，可以以接近O（1）的办法查找，并且不能爆内存
竞赛法（也就是线型探查法）：
预处理：比如说有100000个数字，就开100007个位置（或者再大一点，内存限制足够大的时候我喜欢开499997，但最好是质数或长的像质数），然后把mod设为100007（或刚才的质数）
插入：设插入的是x,那么就把x放入x%mod。
但是，我相信大家已经发现了，比如题目只给了100个数字，mod=107，好，现在x=78，没有问题。再插入一个，17，还是没问题。第三个，x=185，185%107=78，两个重复了！怎么办？就这么凉拌吗？当然是不行的。那我就把x放在79的位置，好，下次插入也一样，假如第四次插入了293，293%107=79,79又被占了！放在80的位置吧。好，木有问题。第五个，10778，10778%107=78。又放在78的位置了。78不行放79，79还不行放80，80还不行就放81，10778最后放进了81的位置。
查找：设查找的是x,那么就查找x%mod的位置。
和上文一样，比如x=87，没有问题。那如果是124呢？124%107=17，但17的位置放的是17而不是124。那就看18的位置，好，没有了，那么肯定124就不存在了。第三个查找，293，发现79放的是185，看下一个，293，有。第四个查找，10778，从78，到79，到80，到81，有，没错。查找完毕。
理想时间复杂度：插入O(1),查找O(1)。
实际时间复杂度：最优O(1)，平均大概是O(1)，最大O(n)（mod足够大可以避免，如果复杂度还是O(n)，那就是你倒8辈子霉了。）
实用法（也就是挂链法）：
预处理：把mod设为100007（或更大的质数），直接挂mod个链表（或vector），链表首用数组存下来。
插入：设插入的是x,那么就把x放入x%mod对应的链表。
还是上面的例子，好，现在x=78，没有问题。再插入一个，17，还是没问题。第三个，x=185，185%107=78，把x放在78号链表尾的位置，好，下次插入也一样，假如第四次插入了293，293%107=79,好，木有问题。第五个，10778，10778%107=78。又放在78的位置了。很简单吧？
查找：设查找的是x,那么就查找x%mod的位置。
和上文一样，比如x=87，查找链表后发现第一个就是78，没有问题。那如果是124呢？124%107=17，但17的链表没有124。那么124肯定就不存在了。第三个查找，293，发现79号链表第一个就是293。第四个查找，10778，78的链表第三个是，没错。查找完毕。
理想时间复杂度：插入O(1),查找O(1)。
实际时间复杂度：最优O(n/mod)，平均大概是O(n/mod)，最大O(n)(实际用途大于理论用途)
修练者
冷知识: map维护一次的时间复杂度为O(logn)
n=元素数
初级启示者
资深天翼
哈希表：对于n个对{key,value}，value可以相同，而key必须不同（查找可以省略value）把它们以接近O（1）的时间放入该表后，可以以接近O（1）的办法查找，并且不能爆内存
竞赛法（也就是线型探查法）：
预处理：比如说有100000个数字，就开100007个位置（或者再大一点，内存限制足够大的时候我喜欢开499997，但最好是质数或长的像质数），然后把mod设为100007（或刚才的质数）
插入：设插入的是x,那么就把x放入x%mod。
但是，我相信大家已经发现了，比如题目只给了100个数字，mod=107，好，现在x=78，没有问题。再插入一个，17，还是没问题。第三个，x=185，185%107=78，两个重复了！怎么办？就这么凉拌吗？当然是不行的。那我就把x放在79的位置，好，下次插入也一样，假如第四次插入了293，293%107=79,79又被占了！放在80的位置吧。好，木有问题。第五个，10778，10778%107=78。又放在78的位置了。78不行放79，79还不行放80，80还不行就放81，10778最后放进了81的位置。
查找：设查找的是x,那么就查找x%mod的位置。
和上文一样，比如x=87，没有问题。那如果是124呢？124%107=17，但17的位置放的是17而不是124。那就看18的位置，好，没有了，那么肯定124就不存在了。第三个查找，293，发现79放的是185，看下一个，293，有。第四个查找，10778，从78，到79，到80，到81，有，没错。查找完毕。
理想时间复杂度：插入O(1),查找O(1)。
实际时间复杂度：最优O(1)，平均大概是O(1)，最大O(n)（mod足够大可以避免，如果复杂度还是O(n)，那就是你倒8辈子霉了。）
实用法（也就是挂链法）：
预处理：把mod设为100007（或更大的质数），直接挂mod个链表（或vector），链表首用数组存下来。
插入：设插入的是x,那么就把x放入x%mod对应的链表。
还是上面的例子，好，现在x=78，没有问题。再插入一个，17，还是没问题。第三个，x=185，185%107=78，把x放在78号链表尾的位置，好，下次插入也一样，假如第四次插入了293，293%107=79,好，木有问题。第五个，10778，10778%107=78。又放在78的位置了。很简单吧？
查找：设查找的是x,那么就查找x%mod的位置。
和上文一样，比如x=87，查找链表后发现第一个就是78，没有问题。那如果是124呢？124%107=17，但17的链表没有124。那么124肯定就不存在了。第三个查找，293，发现79号链表第一个就是293。第四个查找，10778，78的链表第三个是，没错。查找完毕。
理想时间复杂度：插入O(1),查找O(1)。
实际时间复杂度：最优O(n/mod)，平均大概是O(n/mod)，最大O(n)(实际用途大于理论用途)
中级天翼
map的时间复杂度是O(logn)
初级启示者
知识点+1
