1、哈希
image.png
（1）开放寻址法（蹲坑位法）
1、取模找到该位置，若有人在坑里，则继续找，知道有空坑就跳去下一个坑
2、保证取模后的位置在指定的范围中，需要考虑到负数取模的情况
-17 % 10 的计算结果如下：r = (-17) - (-17 / 10) x 10 = (-17) - (-1 x 10) = -7
17 % -10 的计算结果如下：r = 17 - (17 / -10) x (-10) = (17) - (-1 x -10) = 7
-17 % -10 的计算结果如下：r = (-17) - (-17 / -10) x (-10) = (-17) - (1 x -10) = -7
因此，int k = (x % N + N) % N;
3、取N时，需要取比人数多的2~3倍的质数
4、0x3f3f3f3f比10^9次方大，不会被使用到，可以标识为没用过
image.png
开放寻址法代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003, INF = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while(h[t] != INF && h[t] != x)
{
t ++;
if(t == N) t = 0;
}
return t;
}
int main()
{
memset(h, INF, sizeof h);
int n;
scanf("%d", &n);
while(n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == INF) puts("No");
else puts("Yes");
}
}
return 0;
}
（2）拉链法：
红色圈圈要取的是比10^5方大的质数
image.png
拉链法代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003;
int h[N], e[N], ne[N], idx;
void insert(int x)
{
int t = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[t];
h[t] = idx ++;
}
bool find(int x)
{
int t = (x % N + N) % N;
for(int i = h[t];i != -1;i = ne[i])
{
if(e[i] == x)
return true;
}
return false;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
2、快速排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int l, int r)
{
if(l >= r) return ;
int i = l - 1, j = r + 1;
int mid = q[l + r >> 1];
while(i < j)
{
do {i ++;} while(q[i] < mid);
do {j --;} while(q[j] > mid);
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> q[i];
quick_sort(1, n);
for(int i = 1;i <= n;i ++) cout << q[i] << " ";
cout << endl;
return 0;
}
3、归并排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000 + 10;
int n;
int temp[N], q[N];
void merge_sort(int l, int r)
{
if(l >= r) return ;
int mid = l + r >> 1;
merge_sort(l, mid); merge_sort(mid + 1, r);
int i = l, j = mid + 1;
int k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) temp[k ++] = q[i ++];
else temp[k ++] = q[j ++];
}
while(i <= mid) temp[k ++] = q[i ++];
while(j <= r) temp[k ++] = q[j ++];
for(int i = l, j = 0; i <= r;i ++, j ++) q[i] = temp[j];
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> q[i];
merge_sort(1, n);
for(int i = 1;i <= n;i ++) cout << q[i] << " ";
return 0;
}
4、堆排序
如何手写一个堆？
1、插入一个数 heap[++ size ] = x , up(size)
2、求集合当中的最小值 heap[1]
3、删除最小值 heap[1] = heap[size]; size--; down(1)
4、删除任意一个元素 heap[k] = heap[size];size --; up(k)，down(k)
5、修改任意一个元素 heap[k] = x; up(k)，down(k)
注意：4和5中，后两个操作只会执行一个，直接把两个写上，结果不变，不需判断
（1）O(n)的复杂度进行堆化
for(int i = n/2;i >= 1;i--) down(i);
（2）更改堆元素后重建堆时间：
推算过程：循环（n - 1）次，每次都是从根节点往下循环查找，所以每一次时间是,总时间：
,因此，堆排序的时间复杂度为
image.png
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t)
{
swap(h[u], h[t]);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u >>= 1;
}
}
int main()
{
scanf("%d%d", &n, &m);
/*
//O(n)
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for(int i = n / 2;i >= 0;i --) down(i);*/
//O(nlogn)
for(int i = 1;i <= n;i ++)
{
cnt ++;
scanf("%d", &h[cnt]);
up(cnt);
}
while(m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt --];
down(1);
}
puts("");
return 0;
}
网友评论