引题:求出现次数最多的数字
假设:给出N个数字
, 需要求出现次数最多的数字
.
则我们可以使用1个计数器数组来记录每一个数字的出现次数, 然后进行统计即可.
int count[数字] = 出现次数;
int count[数字] += 1;
只需在每次输入时, 利用 数组高效的随机访问 特性, 即可在O(1)时间内完成计数统计. (注意: 这里仅需对输入进行判断即可, 不需要将输入的数字存储下来.)
转化:求出现次数最多的字符串
假设: 给出N个字符串
, 需要求 出现次数最多的字符串
.
思路1: 我们可以用一个 二维的技术数组 将所有的字符串存储下来, 然后再统计出现次数最多的字符串.
缺点: 1. 该思路会将所有输入的字符串存储下来,占据大量的内存空间
缺点: 2. 如果输入的字符串数量巨大, 如有10万个字符串, 而后续的统计操作是线性操作, 每次统计需要遍历10万个字符串, 需要耗费大量时间.
思路2: 不妨延续我们之前处理“求出现次数最多的数字”的思路, 也适用一个一维的计数数组
来解决问题.
因此:
int count[字符串] = 出现次数;
int count[字符串] += 1;
但是!数组的下标要求是一个整数
,我们没法用字符串
作数组的下标!!
嗯,如果有办法将字符串
映射到数字
的话,问题就解决了。
我们称完成这种映射的函数为哈希函数
。
注意:哈希 = 散列, 哈希表(Map/HashTable/HashMap等意思相同) = 散列表. 这2个词语是同一个意思, 有些地方称 哈希表 为 散列表, 也有称为 字典(Dict)的, 但都是同一个东西.
我们现在就来设计一个这样的哈希函数
,并保证哈希函数
满足这2个要求.
1. 对相同的字符串
,每次映射出相同的数字
2. 对不同的字符串
,每次映射出不同的独一无二的字符串
换句话说,如果我们第一次将字符串“abc”
映射到数字233
的话,那么第二次映射字符串“abc”
的话,结果应该也是数字233
.
而且,我们要保证字符串“abcd”
不能映射到数字233
,因为这个数字已经被字符串“abc”
给占据掉了!(若无法保证映射结果的独一无二
的话,便会发生哈希冲突
)
注意:尽管哈希冲突
是无法避免的, 但是我们应当尽可能降低发生的概率.
1个简单的哈希函数 (将字符串映射到数字):
该哈希函数的映射方式: 逐个累加字符的ASCII码值 并同时乘上 该字符所在的位置.
注意: 最后计算出的哈希值
需要%MAXN(即哈希表数组的长度)来保证所求出的哈希值
(即哈希表数组的下标
是合法下标,也就是避免数组越界
)
#define MAXN 1000 /* 哈希函数 */ int Hash(const char * str) { int index = 0; int at = -1; while (str[at++]) { index += ((at + 1) * (str[at] % 'a')) % MAXN; } return index; }
动手实现自己的哈希表!
注意:我们将上文所提到的计数数组
称为哈希表
,而我们自己写的将字符串映射到数字的函数
称为哈希函数
结合上面的知识, 我们可以来解决问题了。
SOJ1377 字符串统计(时间限制:3秒)
需include: stdlib.h, stdio.h, string.h #pragma warning (disable:4996) // 单词长度 #define MAX_LEN 105 /* 哈希表 */ #define MAXN 1000 int map[MAXN]; /* 哈希函数 */ int Hash(const char * str) { int index = 0; int at = -1; while (str[++at]) { index += ((at + 1) * (str[at] % 'a')) % MAXN; } return index; } int main() { int N; scanf("%d", &N); char ans_str[MAX_LEN]; int ans_count = 0; while (N--) { // WARNING: 输入使用gets()会Wrong Answer. char tempStr[MAX_LEN]; scanf("%s", &tempStr); int curCount = map[Hash(tempStr)] += 1; // Update Ans. if (curCount > ans_count) { ans_count = curCount; strcpy(ans_str, tempStr); } } puts(ans_str); }
SOJ1003 第三届程序设计大赛 让气球飞起来
代码与SOJ1377完全相同.
不妨直接使用C++ STL提供的map结构
注意: 使用C++ STL的map时, 若key为字符串, 则需要使用C++的string类.
但是, C的scanf()
和gets()
并不支持输入 string类, 所以只能使用cin
来输入string.
注意: cin
的输入效率比scanf()
差很多, 如果字符串的输入量非常大, 需要重新设置cin
的一些属性, 以加速cin
的输入速度.
在使用cin输入string时, 请加上下面2句代码, 否则将会面临Time Limit Exceed
的问题.
ios::sync_with_stdio(0); cin.tie(0);