哈希算法题目：查找共用字符

字数 2446 2025-10-28 20:05:13

哈希算法题目：查找共用字符

题目描述
给定一个字符串数组 words，其中 words[i] 由小写英文字母组成。需要返回一个数组，包含所有字符串中都出现的字符（包括重复字符）。也就是说，如果一个字符在每个字符串中出现多次，那么结果中也需要包含该字符相应次数。可以按任意顺序返回答案。

解题过程

问题分析
我们需要找出所有字符串中都包含的字符。关键点在于，一个字符要成为“共用字符”，它在每个字符串中出现的次数都必须大于0。而且，这个字符在最终结果中出现的次数，应该等于它在所有字符串中出现次数的最小值。
- 示例：words = ["bella", "label", "roller"]
  - 字符 'l' 在 "bella" 中出现 2 次，在 "label" 中出现 2 次，在 "roller" 中出现 2 次。最小出现次数是 2，所以结果中应有 2 个 'l'。
  - 字符 'e' 在每个字符串中都出现 1 次，最小出现次数是 1，所以结果中应有 1 个 'e'。
  - 字符 'b' 在 "roller" 中未出现，所以它不是共用字符。
核心思路：使用哈希表（频率数组）
由于字符串只包含小写字母，我们可以使用一个长度为 26 的数组来充当哈希表，记录每个字符出现的频率。数组下标 0 对应 ‘a’，下标 1 对应 ‘b’，以此类推，下标 25 对应 ‘z’。
循序渐进步骤

步骤一：初始化全局最小频率数组
我们创建一个数组 minFreq，长度为 26，初始值可以设为一个很大的数（比如无穷大 Infinity），或者第一个单词的频率。这个数组将用于记录每个字符在所有字符串中的最小出现次数。

步骤二：遍历每个单词
对于数组 words 中的每一个单词：
a. 创建一个新的临时频率数组 charCount（长度26，初始值为0），专门用于统计当前这个单词中每个字符出现的次数。
b. 遍历当前单词的每一个字符 c。
* 计算字符 c 对应的数组下标：index = c.charCodeAt(0) - ‘a’.charCodeAt(0)。
* 将 charCount[index] 的值加 1。
c. 现在，我们得到了当前单词的字符频率数组 charCount。接下来，我们需要用这个数组来更新全局的 minFreq 数组。
* 遍历 26 个字母（即遍历 minFreq 数组的 26 个索引位置）。
* 对于每个索引 i，将 minFreq[i] 更新为 minFreq[i] 和 charCount[i] 中的较小值。公式为：minFreq[i] = Math.min(minFreq[i], charCount[i])。
* 这样，在处理完第一个单词后，minFreq 就是第一个单词的频率。处理第二个单词时，minFreq 中每个位置的值都会变成前两个单词中该字符出现次数的较小值。以此类推，当处理完所有单词后，minFreq[i] 的值就是字符 (‘a’ + i) 在所有单词中出现次数的最小值。

步骤三：构建结果数组
经过步骤二，minFreq 数组已经告诉我们每个共用字符应该出现几次。
- 遍历 minFreq 数组的 26 个索引位置。
- 对于每个索引 i，如果 minFreq[i] > 0，说明字符 (‘a’ + i) 是一个共用字符。
- 我们将这个字符重复 minFreq[i] 次，然后加入到结果数组中。
- 例如，如果 minFreq[4] （对应字符 ‘e’）的值为 3，我们就向结果数组中放入三个 ‘e’。
举例说明
以 words = [“bella”, “label”, “roller”] 为例：
- 初始化：minFreq = [Inf, Inf, Inf, ...] (26个无穷大)
- 处理 “bella”：
  - 其频率数组 charCount 为：b:1, e:1, l:2, a:1 (其他为0)。
  - 更新 minFreq：minFreq 变为 [a:1, b:1, e:1, l:2, ...] (其他位置从无穷大变为0，但取最小值后还是0？这里注意，应该是 min(Inf, 1) = 1, min(Inf, 0) = 0。所以最终 minFreq 是每个字母在第一个单词中的出现次数)。
- 处理 “label”：
  - 其频率数组 charCount 为：l:2, a:1, b:1, e:1。
  - 更新 minFreq：对于 ‘a’，min(1, 1) = 1；对于 ‘b’，min(1, 1) = 1；对于 ‘e’，min(1, 1) = 1；对于 ‘l’，min(2, 2) = 2；对于其他字母，min(0, 0) = 0。
- 处理 “roller”：
  - 其频率数组 charCount 为：r:2, o:1, l:2, e:1。
  - 更新 minFreq：
    - ‘a’: min(1, 0) = 0 (因为 “roller” 里没有 ‘a’)
    - ‘b’: min(1, 0) = 0 (因为 “roller” 里没有 ‘b’)
    - ‘e’: min(1, 1) = 1
    - ‘l’: min(2, 2) = 2
    - ‘o’: min(0, 1) = 0
    - ‘r’: min(0, 2) = 0
- 最终 minFreq：只有 ‘e’ 对应位置为 1，’l’ 对应位置为 2。
- 构建结果：1 个 ‘e’，2 个 ‘l’ -> [“e”, “l”, “l”] (顺序不限)。

通过以上步骤，我们利用哈希表（频率数组）高效地统计了字符频率，并通过不断取最小值的方法，找出了所有字符串中的共用字符及其最小出现次数。

哈希算法题目：查找共用字符题目描述给定一个字符串数组 words，其中 words[ i ] 由小写英文字母组成。需要返回一个数组，包含所有字符串中都出现的字符（包括重复字符）。也就是说，如果一个字符在每个字符串中出现多次，那么结果中也需要包含该字符相应次数。可以按任意顺序返回答案。解题过程问题分析我们需要找出所有字符串中都包含的字符。关键点在于，一个字符要成为“共用字符”，它在每个字符串中出现的次数都必须大于0。而且，这个字符在最终结果中出现的次数，应该等于它在所有字符串中出现次数的最小值。示例：words = [ "bella", "label", "roller" ] 字符 'l' 在 "bella" 中出现 2 次，在 "label" 中出现 2 次，在 "roller" 中出现 2 次。最小出现次数是 2，所以结果中应有 2 个 'l' 。字符 'e' 在每个字符串中都出现 1 次，最小出现次数是 1，所以结果中应有 1 个 'e' 。字符 'b' 在 "roller" 中未出现，所以它不是共用字符。核心思路：使用哈希表（频率数组）由于字符串只包含小写字母，我们可以使用一个长度为 26 的数组来充当哈希表，记录每个字符出现的频率。数组下标 0 对应 ‘a’，下标 1 对应 ‘b’，以此类推，下标 25 对应 ‘z’。循序渐进步骤步骤一：初始化全局最小频率数组我们创建一个数组 minFreq ，长度为 26，初始值可以设为一个很大的数（比如无穷大 Infinity ），或者第一个单词的频率。这个数组将用于记录每个字符在所有字符串中的最小出现次数。步骤二：遍历每个单词对于数组 words 中的每一个单词： a. 创建一个新的临时频率数组 charCount （长度26，初始值为0），专门用于统计当前这个单词中每个字符出现的次数。 b. 遍历当前单词的每一个字符 c 。 * 计算字符 c 对应的数组下标： index = c.charCodeAt(0) - ‘a’.charCodeAt(0) 。 * 将 charCount[index] 的值加 1。 c. 现在，我们得到了当前单词的字符频率数组 charCount 。接下来，我们需要用这个数组来更新全局的 minFreq 数组。 * 遍历 26 个字母（即遍历 minFreq 数组的 26 个索引位置）。 * 对于每个索引 i ，将 minFreq[i] 更新为 minFreq[i] 和 charCount[i] 中的较小值。公式为： minFreq[i] = Math.min(minFreq[i], charCount[i]) 。 * 这样，在处理完第一个单词后， minFreq 就是第一个单词的频率。处理第二个单词时， minFreq 中每个位置的值都会变成前两个单词中该字符出现次数的较小值。以此类推，当处理完所有单词后， minFreq[i] 的值就是字符 (‘a’ + i) 在所有单词中出现次数的最小值。步骤三：构建结果数组经过步骤二， minFreq 数组已经告诉我们每个共用字符应该出现几次。遍历 minFreq 数组的 26 个索引位置。对于每个索引 i ，如果 minFreq[i] > 0 ，说明字符 (‘a’ + i) 是一个共用字符。我们将这个字符重复 minFreq[i] 次，然后加入到结果数组中。例如，如果 minFreq[4] （对应字符 ‘e’）的值为 3，我们就向结果数组中放入三个 ‘e’。举例说明以 words = [“bella”, “label”, “roller”] 为例：初始化： minFreq = [Inf, Inf, Inf, ...] (26个无穷大) 处理 “bella” ：其频率数组 charCount 为：b:1, e:1, l:2, a:1 (其他为0)。更新 minFreq ： minFreq 变为 [ a:1, b:1, e:1, l:2, ...] (其他位置从无穷大变为0，但取最小值后还是0？这里注意，应该是 min(Inf, 1) = 1 , min(Inf, 0) = 0 。所以最终 minFreq 是每个字母在第一个单词中的出现次数)。处理 “label” ：其频率数组 charCount 为：l:2, a:1, b:1, e:1。更新 minFreq ：对于 ‘a’， min(1, 1) = 1 ；对于 ‘b’， min(1, 1) = 1 ；对于 ‘e’， min(1, 1) = 1 ；对于 ‘l’， min(2, 2) = 2 ；对于其他字母， min(0, 0) = 0 。处理 “roller” ：其频率数组 charCount 为：r:2, o:1, l:2, e:1。更新 minFreq ： ‘a’: min(1, 0) = 0 (因为 “roller” 里没有 ‘a’) ‘b’: min(1, 0) = 0 (因为 “roller” 里没有 ‘b’) ‘e’: min(1, 1) = 1 ‘l’: min(2, 2) = 2 ‘o’: min(0, 1) = 0 ‘r’: min(0, 2) = 0 最终 minFreq ：只有 ‘e’ 对应位置为 1，’l’ 对应位置为 2。构建结果：1 个 ‘e’，2 个 ‘l’ -> [“e”, “l”, “l”] (顺序不限)。通过以上步骤，我们利用哈希表（频率数组）高效地统计了字符频率，并通过不断取最小值的方法，找出了所有字符串中的共用字符及其最小出现次数。