流离之人追逐幻影

用户名：pwj666

访问量：60217

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （Java代码）

散列定义与整数散列-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-06-21 12:25:31 浏览：668　|　评论：0　

散列（hash） 是常用的算法思想之一，在很多程序中都会有意无意的使用到。接下来以问题驱动来进行学习。

先来看一个简单的问题来阐述散列的思想：
```
给出N个正整数，再给出M个正整数，问这M这个数的每个数是否在N个数中出现过，其中N，M<=10^5,且所有正整数均不超过10^5.
```
```
例如：
N=5，M=3， N个正整数为{8,3,7,6,2}，欲查询的M个正整数为{7,4,2}，于是后者中只有7和2在N个正整数中出现过，而4是没有出现过。
```

```
对于这个问题，最直观的思路就是，在M中对于每个欲查询的正整数x，遍历N所有中所有的正整数y，看是否有一个数与x相等，这种做法的时间复杂度为O(MN)，当N和M都很大的时候（10^5级别），显然是无法承受的。
```
```
有一个新思路——用空间换时间，设定一个bool型数组hashTable[100010]，其中hashTable[x]==true表示正整数x在N个正整数中出现过，而hashTable[x]==false表示正整数x在N个正整数中没有出现过。这样就可以在读入N个正整数可以预处理，即当读入数为x时，令hashTable[x]==true（说明：hashTable数组需要初始化为false，表示初始状态下所有数都未出现过）。于是对M个数欲查询的数，就能直接通过hashTable数组判断每个数是否出现过。这种方法的时间复杂度O(N+M)。
```
```
#include<cstdio>
const int maxn = 100010;
bool hashTable[maxn] = { false };
int main() {
	int n, m, x;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		hashTable[x] = true;//数字x出现
	}
	for (int i = 0; i < m; i++) {
		scanf("%d", &x);
		if (hashTable[x] == true) {    //如果数字x出现过，则输出YES
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	return 0;
}
```
```
如果题目要求M个欲查询的数中每个数在N个数中出现的次数，那么可以把hashTable数组替换为int型，然后再输入N个数时进行预处理，即当输入数为x时，就令hashTable[x]++,这样就可以用O(N+M)的时间复杂度输出每个欲查询的数出现的次数。
```
```
#include<cstdio>
const int maxn = 100010;
int hashTable[maxn] = {0};
int main(){
	int n,m,x;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		hashTable[x]++;
	}
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		printf("%d\n",hashTable[x]);
	}
	return 0;
}
```
**这两个问题都有一个特点，那就是直接把输入的数作为数组的下标来对这个数的性质进行统计（这种做法非常实用，务必掌握）。**
以上两个方法虽然好，但也只能解决一部分这方面问题，如果输入的数非常大呢（十的九次方以上），如果输入的是一个字符串呢，就不能直接将输入的内容作为数组下标了。这就引出了散列（hash）.如果需要可以看看数据结构中散列表那章节的内容，加深理解。 我也先放着，准备相关的题目进行练习。做完题目再进行下一步的深入探讨。

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （Java代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

散列定义与整数散列-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

数组输出（C语言代码）

剔除相关数（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （Java代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

散列定义与整数散列-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

数组输出 （C语言代码）

剔除相关数 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

　　评论区

数组输出（C语言代码）

剔除相关数（C语言代码）