【卡码网Python基础课 16.出现频率最高的字母】

题目描述与分析

描述

题目描述：
给定一个只包含小写字母的字符串，统计字符串中每个字母出现的频率，并找出出现频率最高的字母，如果最高频率的字母有多个，输出字典序靠前的那个字母。

输入描述
包含多组测试数据，每组测试数据占一行。

输出描述
有多组输出，每组输出占一行。

输入示例：

2
abcdeef
aabbccddeeff

输出示例：

e
a

2.分析

之前学习的数组（列表）、字符串、链表等数据结构，如果想找到其中某个元素或某个节点，需要从索引为0的位置或者链表头节点开始，逐一进行比较，直到找到相等的位置或者末尾才会结束。

要想避免之前的比较，直接通过查找记录找到存储位置可以通过哈希表来实现。哈希表是根据关键码key的值而直接进行访问的数据结构。

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

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

哈希表来解决问题的时候，一般选择以下三种数据结构：
数组（列表）
集合
映射

一、哈希表

哈希表（也称为散列表）是一种使用哈希函数组织数据以支持快速插入和搜索的数据结构。哈希表在平均时间复杂度上提供快速的数据访问，通常为O(1)。哈希表通过将键通过哈希函数转换为数组索引来直接访问内存存储位置。

哈希表的原理：
哈希表的核心是哈希函数，它将输入（通常是键）转换为一个整数，这个整数则被用作数组的索引。理想情况下，哈希函数应该将键均匀分布在哈希表的索引中，但实际上总会有一些碰撞（即不同的键产生相同的索引）。

处理哈希表中的碰撞有几种常见的方法：

1.开放寻址（Open Addressing）：当发生碰撞时，通过某种探测方法（如线性探测、二次探测或双重哈希）寻找另一个空槽来存储值。
2.链表法（Chaining）：每个数组索引处存储一个指向键和值列表（通常是链表）的指针。如果多个键映射到相同的索引，它们都可以存储在这个位置的列表中。

在Python中，字典（dict）是哈希表的一种实现。Python的字典允许以键值对的形式存储数据，其中键必须是不可变类型，如整数、浮点数、字符串或元组。

# 创建一个字典
my_dict = {'apple': 'red', 'banana': 'yellow', 'cherry': 'red'}# 访问字典
print(my_dict['apple'])  # 输出: red# 添加一个新的键值对
my_dict['orange'] = 'orange'# 检查键是否存在
if 'banana' in my_dict:print("Banana is in the dictionary.")# 遍历字典
for key, value in my_dict.items():print(f"{key}: {value}")# 删除一个元素
del my_dict['cherry']

哈希表可以将其比喻为一个大抽屉，抽屉里面有很多小格子。每个格子可以用来存放一些东西。

抽屉编号：抽屉有编号，这个编号就是数据的key，我们通过这个key来找到对应的抽屉。
散列函数：哈希表使用一种特殊的函数（哈希函数），来决定数据应该放在哪个抽屉里。这个函数将数据的名字key转换成一个数字，然后根据这个数字来选择一个抽屉。
抽屉里的物品：在每个抽屉里，可以放一些东西，这些东西就是我们要存储的数据。
解决冲突：有时候不同的key经过散列函数后可能会得到相同的编号，这就是冲突。哈希表有方法来处理这些冲突。
快速查找：当我们需要找到某个数据时，哈希表可以通过名字key快速地找到对应的抽屉，然后取出里面的数据，这个操作非常快速，就像从抽屉中拿出东西一样。

二、代码编写

首先，需要接收整数 n 的输入，表示共有 n 行测试数据，然后进行 n 次循环迭代，接收一行字符串作为输入，将字符串经过处理后，统计输出最高频率的字母。

# n 表示
n = int(input())for _ in range(n):s = input()

统计字符串中各个字符的频率可以定义一个长度为26的列表，列表的元素代表着各位字符的频率，初始频率都为0，列表的索引 0 对应着字符 a, 索引 1 对应着字符 b, 依次类推，索引 25 对应着字母 z。

然后遍历整个字符串，如果遇到字符 a, 则对应的索引0 的元素值 + 1，表示频率 + 1，当字符串遍历完毕，各个字符的频率也都统计完毕了。

示例图如下：在字符串 "abceef"当中，字符 a 对应索引0，所在位置元素的值为1，字符 b、c、f类似，字符 e 对应索引 4，所在位置元素的值为2，表示频率为2。
在这里插入图片描述
当字符串遍历过程中，假设 char 表示当前字符，只需要计算 ord(char) - ord(‘’)就可以计算出当前字符和字符 'a’之间的 Unicode 码值，这个差值就是列表元素的索引。

假设字符 char 为’a’, ord(‘a’) - ord(‘a’)为 0, 索引 0 所在的位置的计数 + 1，假设字符 c 为’b’, ord(‘b’) - ord(‘a’)的值为 1，索引 1 所在的位置的计数 + 1，其他字符依次类推。

# 列表复制，将 0 这个元素复制了26次，从而创建了包含26个 0 的列表
temp = [0] * 26
# 遍历字符串    
for char in s:# ord(char) - ord('a') 表示当前字符和字符'a'之间的 Unicode码值，也是对应列表的索引a = ord(char) - ord('a')# tem[索引]处的值 + 1temp[a] += 1

经过一轮遍历之后已经完成统计，数组中各位的元素已经是a-z字母的频次了，但是如果想要找到最大值，还是需要重新遍历一遍，那我们如何找到这个最大值呢？

这需要先初始化一个字符的最大出现频率，然后头开始遍历，逐一比对当前字符出现的频次和最大频率的大小，如果当前字符出现的频次大于最大值，则更新最大值为当前字符出现的频次，这样完整遍历一遍后，就能找到字符的最大出现频率。

# 初始化字符的最大出现频率为0
maxFreq = 0
# 循环迭代处理列表中的其他字符
for i in range(26):# 如果当前字母的出现频率大于 maxFreqif temp[i] > maxFreq:# 更新 maxFreq 为当前字母的出现频率maxFreq = temp[i]

但是上面的操作只统计了最大频率，并没有记录最大频率所在的索引i

maxFreq = 0
# 在还没有遍历temp列表之前，不知道哪个字符是出现频率最高的，用-1来表示“尚未找到”。
maxFreqChar = -1for i in range(26):# 如果当前字母的出现频率大于 maxFreqif temp[i] > maxFreq:maxFreq = temp[i]# 记录当前字母的索引maxFreqChar = i

当循环结束后，已经找到出现频率最大字符的频次以及对应的索引i，将 'a’对应的 Unicode 码值加上索引值，就是出现频率最大的字符的 Unicode 码值，再经过chr()函数转换，就能得到最终的结果。

# ord('a') + maxFreqChar 表示 出现频率最大的字符的 Unicode 码值
# chr() 将 Unicode 码值转为对应的字符
res = chr(ord('a') + maxFreqChar)
print(res)

本道题的完整代码如下：

n = int(input())for _ in range(n):s = input()# 创建一个 长度为26，元素都为0的列表temp = [0] * 26for char in s:# 计算字符在列表中对应的索引a = ord(char) - ord('a')# 索引对应的值 + 1temp[a] += 1maxFreq = 0maxFreqChar = -1# 遍历列表，找到最大频率字符的索引for i in range(26):if temp[i] > maxFreq:maxFreq = temp[i]# maxFreqChar为对应的索引maxFreqChar = i# 根据索引转换对应的字符res = chr(ord('a') + maxFreqChar)print(res)