卡码网语言基础课 ｜出现频率最高的字母

@[TOC]卡码网语言基础课 ｜出现频率最高的字母

哈希表

哈希表是根据关键码key的值而直接访问的数据结构。

哈希表的作用是判断一个元素是否出现在集合里，它的核心思想是在关键码和存储位置之间建立一个确定的对应关系，使得每个关键字key对应一个存储位置，而这个对应关系，称之为散列函数（哈希函数）。

实际上，数组就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。

代码编写

基础结构如下：

#include 
#include 
using namespace std;

int main () {
	int n;
	string s;
	
	while (cin >> n) {
		while (n--) {
			cin >> s;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数组可以作为简单哈希表来使用，所以我们可以定义一个数组，来记录字符串s当中字符出现的次数。

由于输入的全都是小写字母，小写字母只有26个，那我们定义一个长度为26的数组即可，字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

在遍历字符串 s 的时候，只需要将s[i] - 'a'所在的索引 + 1即可，并不需要记住字符 a 的ASCII码，只需要求出一个相对的数值。

for (int i = 0; i < s.size(); i++) {
	count[s[i] - 'a']++;
}
1
2
3

经过一轮遍历之后完成统计，数组中各个位元素已经是a-z的频次了，如果想要找到最大值，还需要重新遍历一遍，只需要初始化最大值，然后逐一比对字符出现的频率和当前最大值的大小，如果当前字符出现的频次大于最大值，则更新最大值为当前字符出现的频次，这样完整遍历一遍后，就能找到出现频次最大的字符。

int flag = 0;
char result;

for (int i = 0; i < 26; i++) {
	if (count[i] > flag) {
		flag = count[i];
		result = i + 'a';
	}
}

cout << result << endl;
1
2
3
4
5
6
7
8
9
10
11

完整代码如下：

#include 
#include 
using namespace std;

int main () {
	int n;
	string s;
	
	while (cin >> n) {
		while (n--) {
			cin >> s;
			int count[26] = {0};
			
			for (int i = 0;i < s.size(); i++) {
				count[s[i] - 'a']++;
			}
			int flag = 0;
			char result;
			
			for (int i = 0; i < 26; i++) {
				if (count[i] > flag) {
					flag = count[i];
					result = i + 'a';
				}
			}
			cout << result << endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29