力扣1002题C++解法详解

问题解构与核心逻辑给定一个字符串数组words要求返回一个列表其中包含在所有字符串中都出现的字符。字符区分大小写题目说明中均为小写字母。关键约束如下共有性结果中的每个字符必须在数组中的每一个字符串里都出现过。最小频率若一个字符在不同字符串中出现的次数不同则它在结果中出现的次数应为在所有字符串中出现次数的最小值。输出结果以字符串列表vectorstring形式返回每个字符作为一个独立的字符串元素。例如输入words [bella,label,roller]字符‘l’在三个字符串中分别出现2、2、2次因此结果中加入两个l字符‘e’分别出现1、1、1次结果中加入一个e。输出为[e,l,l]。C解法数组计数法由于字符限定为小写字母可以使用长度为26的整型数组作为哈希表来统计字符频率这是最高效的方法。算法步骤初始化最小频率数组创建一个vectorint minFreq(26, INT_MAX)用于记录每个字符‘a‘ 到 ’z‘在所有字符串中的最小出现次数。初始值设为极大值便于后续取最小值。遍历字符串数组对每个字符串word创建一个临时数组charCount(26, 0)统计其字符频率。遍历word中的每个字符对应charCount索引c - a加1。遍历26个字母将minFreq的每个位置更新为min(minFreq[i], charCount[i])。构建结果遍历minFreq数组将出现次数大于0的字符按其最小频率值重复转换为字符串并添加到结果向量中。C代码实现#include vector #include string #include algorithm #include climits // 用于INT_MAX using namespace std; class Solution { public: vectorstring commonChars(vectorstring words) { // 步骤1初始化最小频率数组 vectorint minFreq(26, INT_MAX); // 步骤2遍历所有单词更新最小频率 for (const string word : words) { vectorint charCount(26, 0); // 统计当前单词的字符频率 for (char c : word) { charCount[c - a]; } // 更新全局最小频率 for (int i 0; i 26; i) { minFreq[i] min(minFreq[i], charCount[i]); } } // 步骤3根据最小频率构建结果 vectorstring result; for (int i 0; i 26; i) { // 将字符 (char)(a i) 重复 minFreq[i] 次加入结果 for (int j 0; j minFreq[i]; j) { // 使用 emplace_back 直接在容器末尾构造字符串效率优于 push_back result.emplace_back(1, a i); } } return result; } };代码关键点解析minFreq初始化为INT_MAX确保第一次与charCount取min时能正确更新为charCount的值。内层循环for (char c : word)遍历字符串的简便写法。c - a将字符 ‘a’-‘z‘ 映射到数组索引 0-25 的标准方法。result.emplace_back(1, a i)这是构建结果的关键。emplace_back直接在result向量的末尾构造一个字符串对象该字符串由1个字符(‘a’ i)组成。这比先创建临时字符串再用push_back更高效。复杂度分析时间复杂度O(N * M)其中N是数组words的长度M是数组中字符串的平均长度。我们需要遍历每个字符串的每个字符两次一次统计一次更新最小值但常数项可以忽略仍为线性复杂度。空间复杂度O(1)或O(∣Σ∣)其中∣Σ∣是字符集大小此处为26。我们只使用了固定大小的辅助数组与输入数据规模无关。与其他解法的对比为了更全面理解下表将本解法与另一种常见的哈希表unordered_map解法进行对比特性数组计数法推荐哈希表法unordered_map数据结构固定大小的vectorint大小26unordered_mapchar, int适用场景字符集已知且较小如小写字母字符集未知或较大如Unicode时间复杂度O(N * M)访问数组为O(1)O(N * M)哈希表操作平均O(1)空间复杂度O(1)O(∣Σ∣)但常数开销更大性能更优。内存连续CPU缓存友好无哈希冲突开销。稍差。涉及哈希计算和动态内存管理。代码简洁性简单直观相对复杂需要处理键不存在的情况对于本题仅小写字母数组计数法是绝对最优选择其效率远高于哈希表法。关联题目与模式总结此题的本质是求多个集合每个字符串的字符频次的交集且交集中元素的重数取其在各集合中出现次数的最小值。这种“计数取最小”的模式可以推广到一系列问题题目核心操作与本题的关联1002. 查找常用字符求多个字符串的字符频率最小交集本题本身349. 两个数组的交集求两个数组的唯一公共元素集合简化版只求是否存在不统计次数350. 两个数组的交集 II求两个数组的公共元素并保留最小出现次数可以看作本题在两个“字符串”数组上的特例242. 有效的字母异位词比较两个字符串的字符频率是否完全相同使用相同的数组计数技术掌握这种基于固定数组的频次统计与比较方法是解决许多字符串处理与哈希类问题的基础技能。参考来源1002. Find Common Characters*leetcode 1002. 查找常用字符leetcode-1002查找常用字符LeetCode第349题_两个数组的交集LeetCode第313题_超级丑数Leetcode 1002查找常用字符