引题：求出现次数最多的数字

假设：给出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结构

延续上面的思路，我们也可以不必自己动手实现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);

来做题目叭

SOJ1003 第三届程序设计大赛 让气球飞起来

SOJ1377 字符串统计(时间限制：3秒)

通解代码