哈希与二分

哈希

什么是哈希

哈希一般以哈希表的形式使用，哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

哈希有什么用

哈希是一种很高效的数据结构。哈希最大的优点就是可以快速的查询一个数是否存在于数组中，如果哈希的冲突处理得当的话，那么每次查询都可以在很小的常数内完成。

处理冲突的方法

1. 线性探测法

冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

2. 平方探测法

冲突发生时，在表的左右进行跳跃式探测，比较灵活。

首先来说假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。
　　考虑模是合数的情况：假设N = kn, M = km， N和M存在最大公因数k，此时可以将N % M = r转化为公式N = Mq + r，即kn = kmq + r。其中q是商，r是余数。“表面上”r的取值范围是{0, 1, 2, …, M-1}（忽视了只有N与M最大公因数为1时，才能取整个余数集合R的定理），一片和谐。但是可以对公式进行稍微的变换，n = mq + (r/k)，由于n和mq都是整数，则(r/k)也是整数。此时我们看一看到(r/k)的取值范围是{0, 1, 2, …, m} = {0, 1, 2, …, M/k}。恢复到原式，也是就r的“实际”取值范围是{0, k, 2k, 3k, …, m*k}，缩小了k倍。
　　可以明显看出，在模和关键字有公因数的情况下，模后取值范围减少，冲突概率增加，尤其是关键字是等差数列。而模为质数就不会出现这种情况。

二分

二分查找法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间，但它有一个前提，就是必须在有序数据中进行查找。
时间复杂度：O(n) ----> O(logⁿ)

Description
给你一个序列，然后给你m个元素，让你从序列中找出与每个元素最接近的数字输出来，如果有两个就输出两个。
Input
多组输入，第一行给你两个数n（0 < n < 10000000）,m(0 < m < n),接下来是数列的n个数，然后再输入m个元素，让你找出最接近每个元素的值。如果有两个，按从小到大输出。
Output
这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;typedef long long ll;const int N = 1e7+10;int n;
int a[N];void solve(int key)
{int l = 0, r = n-1;while(l <= r){int mid = (l+r)/2;if(a[mid] == key){printf("%d\n", a[mid]);return ;}else{if(key > a[mid]) l = mid+1;else r = mid-1;}}if(r == -1 || l == n){if(r == -1) printf("%d\n", a[0]);else printf("%d\n", a[n-1]);}else{if(key-a[r] == a[l]-key) printf("%d %d\n", a[r], a[l]);else if(key-a[r] > a[l]-key) printf("%d\n", a[l]);else printf("%d\n", a[r]);}
}int main()
{int m, x;while(~scanf("%d %d", &n, &m)){for(int i = 0; i < n; i++){scanf("%d", &a[i]);}sort(a, a+n);while(m--){scanf("%d", &x);solve(x);}printf("\n");}return 0;
}

数据结构实验之查找七：线性之哈希表

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;typedef long long ll;const int N = 1510;int n;
int Hash[N];int main()
{int p;int x;while(~scanf("%d %d", &n, &p)){memset(Hash, -1, sizeof(Hash));for(int i = 0; i < n; i++){scanf("%d", &x);int tmp = x%p;if(Hash[tmp] == -1){printf("%d", tmp);Hash[tmp] = x;}else{int flag = 0;for(int j = 0; j < p; j++){if(Hash[j] == x){printf("%d", j);flag = 1;break;}}if(!flag){while(Hash[tmp%p] != -1) tmp++;Hash[tmp%p] = x;printf("%d", tmp%p);}}if(i == n-1) printf("\n");else printf(" ");}}return 0;
}

数据结构实验之查找五：平方之哈希表

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;typedef long long ll;const int N = 2010;int n;
int Hash[N];int main()
{int p, x;while(~scanf("%d %d", &n, &p)){memset(Hash, -1, sizeof(Hash));for(int i = 0; i < n; i++){scanf("%d", &x);int tmp = x%p;if(Hash[tmp] == -1){printf("%d", tmp);Hash[tmp] = x;}else{for(int j = 1; j <= p-1; j++){if(Hash[(x+j*j)%p] == -1){printf("%d", (x+j*j)%p);Hash[(x+j*j)%p]++;break;}else if(Hash[(x-j*j)%p] == -1){printf("%d", (x-j*j)%p);Hash[(x-j*j)%p]++;break;}}}if(i == n-1) printf("\n");else printf(" ");}}return 0;
}

二分练习
数据结构实验之查找四：二分查找

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！