【代码随想录python笔记整理】第十六课 · 出现频率最高的字母

前言:本笔记仅仅只是对内容的整理和自行消化，并不是完整内容，如有侵权，联系立删。

一、哈希表初步  

       在之前的学习中，我们使用数组、字符串、链表等等，假如需要找到某个节点，则都要从头开始，逐一比较，直到找到为止。为了能够直接通过要查找的记录找到其存储位置，我们选择使用哈希表实现此功能。哈希表其实就是通过一个关键码 key 的值而直接进行访问的数据结构。

       哈希表的作用是快速判断一个元素是否出现在集合，它通过在关键码和存储位置之间建立一个确定的对应关系 F(key) ，使得每个关键字 key 对应一个存储位置，而这个对应关系，称之为散列函数（哈希函数）。哈希表来解决问题的时候，一般选择以下三种数据结构：数组、集合、映射。

二、最简单的一个数组案例

       下面我们来看一个有哈希思想的程序案例，但实质上这个程序和哈希表的应用关系不大。主要是帮助我们理解哈希表是什么，它的核心思想是什么。

       对于这个问题，我们可以这样想：想要找出出现频率最高的字母，我们至少需要遍历一遍整个字符串，因此尽可能在这一遍中完成所有任务。

       为了实现这个目的，我们可以将26个字母按次序存储在一个数组中，而数组的索引和字母实现了一一对应，如果把 ASCLL 码和索引的关系写出来，那就是 ASCLL - 97 = 索引。这就是一种哈希函数。所以我们也常常把数组称为是最简单的一种哈希表。

       接下来，我们在遍历过程中，将遇到的每个字符都记为出现 1 次，并将其对应索引的位置数值加一。在完成遍历后，显然我们还需要找出索引位置处数值最大的是哪个字符，以及出现了多少次。为实现这一步，我们又需要重新遍历一遍字符串。

三、代码展示

n = int(input())

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

四、总结

       本节内容我们学习到了数组（列表）作为哈希表的使用，下节课我们会学习哈希表的另外一种形式`set集合`。