第一次碰到力扣49题字母异位词分组的时候我差点被它人畜无害的外表骗了。题目给一个字符串数组让把由相同字母重排而成的单词归到一组一听就是送分题把每个字符串排序排序结果一样的放进同一组不就行了可真当用C语言写起来我才发现难点根本不在“排序判等”而在于“把字符串放进对应组”这个动作需要一套能快速查找的数据结构。Python里一行字典动作的事在C语言里得完整手写一张哈希表。这篇文章就记录我的完整实现、设计取舍以及本地调试时踩过的坑。适合正在用C语言刷力扣、特别是对“手写哈希表”比较头疼的读者。1. 题目拆解异位词判定是分组的第一步1.1 题目到底让你做什么输入strs是一个字符串指针数组每个元素是一个单词。输出要求是一个“分组的数组”每个分组里放原单词的指针。示例里面[eat,tea,tan,ate,nat,bat]的输出是[[bat],[nat,tan],[ate,eat,tea]]组内和组间的顺序都不要求。题目有三条硬约束直接决定方案strsSize范围是 1 到 10000每个单词长度 0 到 100并且只包含小写字母。这意味着如果你的算法复杂度是 O(n²) 级别的到了 10000 个单词基本就超时了而 O(n * klogk) 或者 O(n * k) 才能稳定通过其中 n 是单词个数k 是单词平均长度。力扣官方的分类把它归到“哈希表”但它实际考的是两件事第一能不能想到“排序后的字符串作为异位词唯一标识”的建模第二在 C 语言里能不能把这个模型落成代码。第一件事很多语言都能轻松解决第二件事才是 C 语言玩家的分水岭。1.2 判定异位词的三种姿势判定两个字符串是不是异位词我在本地试过三种路线简单对比一下。排序比较把单词复制一份按字母排序ate和eat都会变成aet。两个单词排序后相等就是异位词。优点是键短、直观C 标准库的qsort可以直接用缺点是每个单词都要付出 O(klogk) 的排序成本。计数比较统计 26 个字母出现次数aet和ate的计数都是 a1、e1、t1。可以用“1_0_0_..._0_1_0...”这种编码串当键也可以直接用长度 26 的数组逐位比较。优点是生成键只需要 O(k) 扫一遍缺点是这个编码串固定长达几十个字符哈希计算和strcmp都会变慢。质数乘积给 a 到 z 分别映射 2、3、5、7……这个质数表单词的键就是每个字母对应质数的乘积。因为质因数分解唯一乘积相等等价于异位词。这个思路非常漂亮但实际几乎没法用在本题一个长度 100 的单词全是a2 的 100 次方早就溢出了所以只能当作概念了解。三种选型里代码实现我选了排序比较。原因是本题单词长度小qsort完全扛得住key 又很短哈希表的查找和比较都很快。计数编码作为备选方案更占优势的场景是单词特别长的时候第六节我会再给结论。2. 为什么C语言解法绕不开手写哈希表2.1 分组问题的本质是快速查找题目要求“把相同 key 归入同一组”。如果用最朴素的思路维护一个动态分组列表每来一个新单词遍历已经建好的所有分组把每组代表字符串也排序后和当前 key 做比较那每处理一个单词就要扫描 O(n) 个已有分组总复杂度直接变成 O(n² * klogk)。n 一上万这代码在力扣上是跑不过去的。所以问题的核心变成了我需要一个“键 - 分组编号”的映射结构。在 C 语言标准库里没有字典、没有无序映射你只能自己选方案 A对整个strs数组排序让异位词在排序后相邻再扫一遍分组。这意味着要把“排序后的单词副本”和“原始索引”绑成一个结构体自定义比较函数排序后还要重建分组数组。理论可行但代码复杂度和调试成本一点都不低。方案 B手写哈希表。key 是排序后的单词字符串value 是分组编号gid。新单词来了生成 key 后查表平均 O(1) 命中没命中说明是全新分组。这才是贴合直觉、也是工程上更直接的做法。2.2 哈希表方案的整体流程整个算法可以压缩成一个三步循环key 生成对strs[i]做一份排序副本得到规范化字符串查表并决策用 key 查哈希表。命中则拿到gid未命中说明这是一个新分组申请一个新gid等于当前分组数然后把key - gid插入哈希表结果填充把strs[i]的指针追加到result[gid]这组的末尾并更新这一组的列数colSizes[gid]。整套流程不修改原数组、不移动原字符串最后每组里的每一项都指向原始strs的元素完全符合力扣对返回值的预期。2.3 为什么不用结构体数组加二分查找还有一个看起来可行的方案把所有 key 集中到一个结构体数组里按 key 排序后用bsearch二分查找。但问题在于“新增 key”时数组必须保持有序插入是 O(n) 的移动成本。最坏情况下 10000 个 key数组插入的搬移开销会把二分查找省的这点时间全吃回去甚至更差。这个方案只适合“所有 key 预先已知、之后只查不增”的静态场景和本题边插入边查询的动态需求不匹配。3. 哈希表设计与键生成三个关键决策3.1 键选型排序字符串还是计数序列排序字符串作 key 在代码上最省事因为qsort是现成的。但你要清楚成本在哪里每个单词要先复制再排序。复制是为了不修改原串排序后得到的才是规范化表示。对 10000 个长度 100 的单词qsort的总比较次数大概是 10000 * 100 * log2(100)约 660 万次现代 CPU 上就是一瞬间的事。而计数编码串作 key 的问题在于长度。哪怕单词只有 3 个字母编码串也要覆盖 26 个计数槽还得带分隔符。比如aet的编码可能是1:0:0:0:...1:0:0...光构造这个串就要写一个sprintf循环比较的时候strcmp要走完几十个字符。对短单词来说这比排序法慢不少。我最终选择排序字符串作为 key。但这不是绝对真理——如果你面临的是大量超长单词计数方案反而更合适。决策依据就一条key 的生成成本和 key 本身的比较成本哪个占大头。本题单词短排序成本低key 也短排序法完胜。3.2 哈希函数与桶数量的选择哈希函数的作用是把任意 key 映射到[0, HASH_SIZE-1]的整数。我用了 BKDR 风格static unsigned int hashStr(const char* s) { unsigned int h 0; while (*s) { h h * 31 (unsigned char)(*s); s; } return h % HASH_SIZE; }31是一个经典选择它是质数而且乘法可以优化成(h 5) - h速度不错。注意(unsigned char)的强转不能少否则有符号char在遇到高位为 1 的字符时会出现负数干扰哈希分布。桶数量我选了 10007一个质数。为什么不选 10000因为字符串哈希结果是多项式累加的形式如果桶数是合数比如10000 2^4 * 5^4哈希值低位容易受乘法溢出规律影响分布会出现偏差。质数桶能让映射更平滑。本题最多 10000 个 key10007 个桶平均每个桶连 1 个元素都不到冲突率很低查找效率接近理想的 O(1)。3.3 哈希表里存什么key与gid哈希表节点设计typedef struct HashNode { char* key; int groupIndex; struct HashNode* next; } HashNode;其中key是 malloc 出来的独立字符串绝对不能直接指向makeSortedKey返回的临时 buffergroupIndex记录这个 key 对应的分组在result数组里的下标next是冲突链表的后继指针。插入用头插法新节点挂到对应桶的链表头部。好处是插入 O(1)不用维护尾指针链表顺序对正确性没有任何影响。唯一的注意点是插入时key必须完整拷贝一份否则函数栈上的临时 buffer 一释放哈希表内部就悬空了。4. 完整代码与关键代码段说明4.1 可在本地运行的完整代码下面是完整实现本地可以直接编译运行#include stdio.h #include stdlib.h #include string.h #define HASH_SIZE 10007 typedef struct HashNode { char* key; int groupIndex; struct HashNode* next; } HashNode; typedef struct { HashNode** buckets; } HashMap; static unsigned int hashStr(const char* s) { unsigned int h 0; while (*s) { h h * 31 (unsigned char)(*s); s; } return h % HASH_SIZE; } static int cmpChar(const void* a, const void* b) { return (*(char*)a) - (*(char*)b); } static char* makeSortedKey(const char* s) { int len (int)strlen(s); char* key (char*)malloc(len 1); strcpy(key, s); if (len 0) { qsort(key, len, sizeof(char), cmpChar); } return key; } static HashMap* createMap(void) { HashMap* map (HashMap*)malloc(sizeof(HashMap)); map-buckets (HashNode**)calloc(HASH_SIZE, sizeof(HashNode*)); return map; } static void freeMap(HashMap* map) { for (int i 0; i HASH_SIZE; i) { HashNode* p map-buckets[i]; while (p) { HashNode* next p-next; free(p-key); free(p); p next; } } free(map-buckets); free(map); } static int findGroup(HashMap* map, const char* key) { unsigned int h hashStr(key); HashNode* p map-buckets[h]; while (p) { if (strcmp(p-key, key) 0) { return p-groupIndex; } p p-next; } return -1; } static void insertGroup(HashMap* map, const char* key, int groupIndex) { unsigned int h hashStr(key); HashNode* node (HashNode*)malloc(sizeof(HashNode)); node-key (char*)malloc(strlen(key) 1); strcpy(node-key, key); node-groupIndex groupIndex; node-next map-buckets[h]; map-buckets[h] node; } char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) { HashMap* map createMap(); int capacity 16; char*** result (char***)malloc(sizeof(char**) * capacity); int* colSizes (int*)malloc(sizeof(int) * capacity); int groupCount 0; for (int i 0; i strsSize; i) { char* key makeSortedKey(strs[i]); int gid findGroup(map, key); if (gid -1) { if (groupCount capacity) { capacity * 2; result (char***)realloc(result, sizeof(char**) * capacity); colSizes (int*)realloc(colSizes, sizeof(int) * capacity); } gid groupCount; result[gid] (char**)malloc(sizeof(char*)); result[gid][0] strs[i]; colSizes[gid] 1; insertGroup(map, key, gid); } else { int newLen colSizes[gid] 1; result[gid] (char**)realloc(result[gid], sizeof(char*) * newLen); result[gid][colSizes[gid]] strs[i]; colSizes[gid] newLen; } free(key); } freeMap(map); *returnSize groupCount; *returnColumnSizes colSizes; return result; }4.2 核心代码段为什么这样写result和colSizes的初始容量是 16满了就翻倍。这是典型的动态数组扩容策略realloc会在需要时自动搬移内存翻倍扩容保证平均每次插入 O(1) 的分摊成本。为什么不用固定strsSize因为分组数量在遍历前是未知的用动态扩容可以精确匹配实际分组数也不会浪费太多内存。每组内部的char**数组用realloc按 1 个指针递增扩容。严格地说这种逐次1扩容在单组元素很多时会有一定搬运开销但本题 n 最大才 10000单组最多也就 10000 个指针直接在判题环境是没问题的。真正追求极致的人会在第六节看到“翻倍扩容”的优化思路。findGroup返回-1表示“没找到”。这个哨兵值非常安全因为分组编号从 0 开始永远不会是负数。查到已有分组时代码直接把新指针追加到该组末尾查不到时就先扩容外层数组、再创建新组并把key - gid写进哈希表。最后freeMap的顺序很讲究先取next指针再释放当前节点的key和节点本身接着才往前走。如果反过来先释放节点next就悬空了后面整条链表都会泄漏。5. 本地调试中踩过的四个坑5.1 空字符串与len等于0时的qsort最容易被忽略的是空字符串。strs里可能混入strlen()等于 0如果直接qsort(key, 0, sizeof(char), cmpChar)C 标准并没有明确规定qsort对 0 个元素的行为虽然多数实现会原样返回但严谨一点还是要加上if (len 0)的保护。另外一个和空串相关的问题是边界测试本地验证时[, ]这两个空串应该被分到同一组result[0]里有两个元素两个元素都指向空串。我第一版代码忘了单独测这个用例结果哈希函数返回 0、排序副本是空串逻辑上没问题但如果没有if (len 0)的防护某些环境下qsort会直接崩。5.2 realloc扩容时的指针安全我的示例代码里result realloc(result, ...)这种写法严格来说有一个隐患如果realloc失败它会返回 NULL 并保持原指针不变但你把 NULL 赋给result就等于弄丢了原来的内存块。力扣的判题内存很充足几乎不可能触发所以示例代码保留了这种简洁写法。工程上正确写法是这样char*** tmp (char***)realloc(result, sizeof(char**) * capacity); if (tmp ! NULL) { result tmp; } else { // 不要覆盖 result原指针还可以继续用 }colSizes同理。如果你在本地用 AddressSanitizer 跑记得同时检查这个细节。5.3 哈希表释放顺序freeMap里最容易写错的是这个顺序HashNode* next p-next; free(p-key); free(p); p next;很多人会先free(p)再去拿p-next这就是典型的悬空指针访问。链表节点释放时必须先把后继节点保存下来。另一个容易漏的是p-key。哈希表的 key 在插入时是malloc出来的独立字符串释放节点前必须单独free(p-key)否则每插入一个新键就泄漏一块内存。你可以在本地启用 AddressSanitizer 验证自己的代码有没有泄漏。5.4 三层指针返回值的理解char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes)这个签名第一眼确实吓人。我的理解方式是从右往左拆返回值最外层char***是“分组数组”的指针每个元素是一个分组每个分组是一个char**它是一个“字符串指针的数组”每个字符串是char*指向原始strs里的某个单词。所以result[gid]是第 gid 组的字符串指针数组result[gid][colSizes[gid]] strs[i]就是把当前单词指针放到第 gid 组末尾。一旦把指针层级拆清楚代码里那些[][]就不会看花眼了。6. 复杂度、性能与备选方案对比6.1 时间复杂度到底是多少精确地算一笔账设 n 是字符串个数k 是平均字符串长度。makeSortedKey对每个字符串做一次qsort耗时 O(klogk)总耗时 O(n * klogk)哈希表的查找和插入平均 O(1)但如果 key 很长strcmp需要扫完整个 key也是 O(k)结果填充里每组的realloc分摊到每个指针是 O(1)。所以整体时间复杂度是 O(n * klogk)。这个复杂度在力扣 49 题的所有主流方案里属于优秀水平。空间上哈希表里保存了 n 个 key总长 O(nk)加上桶数组 O(HASH_SIZE) 和结果指针数组 O(n)整体空间复杂度 O(nk HASH_SIZE)。6.2 计数编码和“翻倍容量”两个优化方向如果你觉得排序成本高可以把makeSortedKey替换成计数编码版本统计 26 个字母数量生成一个固定格式的字符串作为 key。生成成本从 O(klogk) 降到 O(k)但 key 变长了几十倍哈希和strcmp又会变慢。我实测在平均长度 10 到 100 的用例下两种方案耗时基本持平单词越长计数编码优势越大。建议你把两种都写了跑一遍对比体会一下“成本转移”的感觉。更值得做的优化是每组内部用翻倍扩容代替逐次1int newCap groupCap[gid] * 2; char** tmp (char**)realloc(result[gid], sizeof(char*) * newCap);这样单组从 1 涨到 10000 只需要大约 14 次 realloc而不是 9999 次对极端数据有明显改善。只是代码里要新增一组groupCap数组逻辑略复杂。力扣 49 的数据规模不大不做也能过但理解这个优化对你以后处理更大规模数据有帮助。6.3 这道题真正教会我的用 C 刷这种“字典类”题目最大的收获不是记住某段模板而是真正理解哈希表为什么存在它把“按键查找”从 O(n) 降到了平均 O(1)。在高级语言里写一行HashMap其实是对底层结构的封装。自己从头写一次才会明白为什么哈希函数要选质数、为什么用链地址法、为什么 key 必须是不可变的拷贝。这些认知不绑定特定语言面试时候手写哈希表也很加分。最后分享一个小体会我后来把这段代码里的哈希函数、链表释放、动态扩容单独抽成了通用模块其它需要“字符串映射到整数”的题目直接复用。力扣上一旦遇到 C 语言的手写哈希表题有这一套兜底心里基本就有底了。
第一次碰到力扣49题字母异位词分组的时候我差点被它人畜无害的外表骗了。题目给一个字符串数组让把由相同字母重排而成的单词归到一组一听就是送分题把每个字符串排序排序结果一样的放进同一组不就行了可真当用C语言写起来我才发现难点根本不在“排序判等”而在于“把字符串放进对应组”这个动作需要一套能快速查找的数据结构。Python里一行字典动作的事在C语言里得完整手写一张哈希表。这篇文章就记录我的完整实现、设计取舍以及本地调试时踩过的坑。适合正在用C语言刷力扣、特别是对“手写哈希表”比较头疼的读者。1. 题目拆解异位词判定是分组的第一步1.1 题目到底让你做什么输入strs是一个字符串指针数组每个元素是一个单词。输出要求是一个“分组的数组”每个分组里放原单词的指针。示例里面[eat,tea,tan,ate,nat,bat]的输出是[[bat],[nat,tan],[ate,eat,tea]]组内和组间的顺序都不要求。题目有三条硬约束直接决定方案strsSize范围是 1 到 10000每个单词长度 0 到 100并且只包含小写字母。这意味着如果你的算法复杂度是 O(n²) 级别的到了 10000 个单词基本就超时了而 O(n * klogk) 或者 O(n * k) 才能稳定通过其中 n 是单词个数k 是单词平均长度。力扣官方的分类把它归到“哈希表”但它实际考的是两件事第一能不能想到“排序后的字符串作为异位词唯一标识”的建模第二在 C 语言里能不能把这个模型落成代码。第一件事很多语言都能轻松解决第二件事才是 C 语言玩家的分水岭。1.2 判定异位词的三种姿势判定两个字符串是不是异位词我在本地试过三种路线简单对比一下。排序比较把单词复制一份按字母排序ate和eat都会变成aet。两个单词排序后相等就是异位词。优点是键短、直观C 标准库的qsort可以直接用缺点是每个单词都要付出 O(klogk) 的排序成本。计数比较统计 26 个字母出现次数aet和ate的计数都是 a1、e1、t1。可以用“1_0_0_..._0_1_0...”这种编码串当键也可以直接用长度 26 的数组逐位比较。优点是生成键只需要 O(k) 扫一遍缺点是这个编码串固定长达几十个字符哈希计算和strcmp都会变慢。质数乘积给 a 到 z 分别映射 2、3、5、7……这个质数表单词的键就是每个字母对应质数的乘积。因为质因数分解唯一乘积相等等价于异位词。这个思路非常漂亮但实际几乎没法用在本题一个长度 100 的单词全是a2 的 100 次方早就溢出了所以只能当作概念了解。三种选型里代码实现我选了排序比较。原因是本题单词长度小qsort完全扛得住key 又很短哈希表的查找和比较都很快。计数编码作为备选方案更占优势的场景是单词特别长的时候第六节我会再给结论。2. 为什么C语言解法绕不开手写哈希表2.1 分组问题的本质是快速查找题目要求“把相同 key 归入同一组”。如果用最朴素的思路维护一个动态分组列表每来一个新单词遍历已经建好的所有分组把每组代表字符串也排序后和当前 key 做比较那每处理一个单词就要扫描 O(n) 个已有分组总复杂度直接变成 O(n² * klogk)。n 一上万这代码在力扣上是跑不过去的。所以问题的核心变成了我需要一个“键 - 分组编号”的映射结构。在 C 语言标准库里没有字典、没有无序映射你只能自己选方案 A对整个strs数组排序让异位词在排序后相邻再扫一遍分组。这意味着要把“排序后的单词副本”和“原始索引”绑成一个结构体自定义比较函数排序后还要重建分组数组。理论可行但代码复杂度和调试成本一点都不低。方案 B手写哈希表。key 是排序后的单词字符串value 是分组编号gid。新单词来了生成 key 后查表平均 O(1) 命中没命中说明是全新分组。这才是贴合直觉、也是工程上更直接的做法。2.2 哈希表方案的整体流程整个算法可以压缩成一个三步循环key 生成对strs[i]做一份排序副本得到规范化字符串查表并决策用 key 查哈希表。命中则拿到gid未命中说明这是一个新分组申请一个新gid等于当前分组数然后把key - gid插入哈希表结果填充把strs[i]的指针追加到result[gid]这组的末尾并更新这一组的列数colSizes[gid]。整套流程不修改原数组、不移动原字符串最后每组里的每一项都指向原始strs的元素完全符合力扣对返回值的预期。2.3 为什么不用结构体数组加二分查找还有一个看起来可行的方案把所有 key 集中到一个结构体数组里按 key 排序后用bsearch二分查找。但问题在于“新增 key”时数组必须保持有序插入是 O(n) 的移动成本。最坏情况下 10000 个 key数组插入的搬移开销会把二分查找省的这点时间全吃回去甚至更差。这个方案只适合“所有 key 预先已知、之后只查不增”的静态场景和本题边插入边查询的动态需求不匹配。3. 哈希表设计与键生成三个关键决策3.1 键选型排序字符串还是计数序列排序字符串作 key 在代码上最省事因为qsort是现成的。但你要清楚成本在哪里每个单词要先复制再排序。复制是为了不修改原串排序后得到的才是规范化表示。对 10000 个长度 100 的单词qsort的总比较次数大概是 10000 * 100 * log2(100)约 660 万次现代 CPU 上就是一瞬间的事。而计数编码串作 key 的问题在于长度。哪怕单词只有 3 个字母编码串也要覆盖 26 个计数槽还得带分隔符。比如aet的编码可能是1:0:0:0:...1:0:0...光构造这个串就要写一个sprintf循环比较的时候strcmp要走完几十个字符。对短单词来说这比排序法慢不少。我最终选择排序字符串作为 key。但这不是绝对真理——如果你面临的是大量超长单词计数方案反而更合适。决策依据就一条key 的生成成本和 key 本身的比较成本哪个占大头。本题单词短排序成本低key 也短排序法完胜。3.2 哈希函数与桶数量的选择哈希函数的作用是把任意 key 映射到[0, HASH_SIZE-1]的整数。我用了 BKDR 风格static unsigned int hashStr(const char* s) { unsigned int h 0; while (*s) { h h * 31 (unsigned char)(*s); s; } return h % HASH_SIZE; }31是一个经典选择它是质数而且乘法可以优化成(h 5) - h速度不错。注意(unsigned char)的强转不能少否则有符号char在遇到高位为 1 的字符时会出现负数干扰哈希分布。桶数量我选了 10007一个质数。为什么不选 10000因为字符串哈希结果是多项式累加的形式如果桶数是合数比如10000 2^4 * 5^4哈希值低位容易受乘法溢出规律影响分布会出现偏差。质数桶能让映射更平滑。本题最多 10000 个 key10007 个桶平均每个桶连 1 个元素都不到冲突率很低查找效率接近理想的 O(1)。3.3 哈希表里存什么key与gid哈希表节点设计typedef struct HashNode { char* key; int groupIndex; struct HashNode* next; } HashNode;其中key是 malloc 出来的独立字符串绝对不能直接指向makeSortedKey返回的临时 buffergroupIndex记录这个 key 对应的分组在result数组里的下标next是冲突链表的后继指针。插入用头插法新节点挂到对应桶的链表头部。好处是插入 O(1)不用维护尾指针链表顺序对正确性没有任何影响。唯一的注意点是插入时key必须完整拷贝一份否则函数栈上的临时 buffer 一释放哈希表内部就悬空了。4. 完整代码与关键代码段说明4.1 可在本地运行的完整代码下面是完整实现本地可以直接编译运行#include stdio.h #include stdlib.h #include string.h #define HASH_SIZE 10007 typedef struct HashNode { char* key; int groupIndex; struct HashNode* next; } HashNode; typedef struct { HashNode** buckets; } HashMap; static unsigned int hashStr(const char* s) { unsigned int h 0; while (*s) { h h * 31 (unsigned char)(*s); s; } return h % HASH_SIZE; } static int cmpChar(const void* a, const void* b) { return (*(char*)a) - (*(char*)b); } static char* makeSortedKey(const char* s) { int len (int)strlen(s); char* key (char*)malloc(len 1); strcpy(key, s); if (len 0) { qsort(key, len, sizeof(char), cmpChar); } return key; } static HashMap* createMap(void) { HashMap* map (HashMap*)malloc(sizeof(HashMap)); map-buckets (HashNode**)calloc(HASH_SIZE, sizeof(HashNode*)); return map; } static void freeMap(HashMap* map) { for (int i 0; i HASH_SIZE; i) { HashNode* p map-buckets[i]; while (p) { HashNode* next p-next; free(p-key); free(p); p next; } } free(map-buckets); free(map); } static int findGroup(HashMap* map, const char* key) { unsigned int h hashStr(key); HashNode* p map-buckets[h]; while (p) { if (strcmp(p-key, key) 0) { return p-groupIndex; } p p-next; } return -1; } static void insertGroup(HashMap* map, const char* key, int groupIndex) { unsigned int h hashStr(key); HashNode* node (HashNode*)malloc(sizeof(HashNode)); node-key (char*)malloc(strlen(key) 1); strcpy(node-key, key); node-groupIndex groupIndex; node-next map-buckets[h]; map-buckets[h] node; } char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) { HashMap* map createMap(); int capacity 16; char*** result (char***)malloc(sizeof(char**) * capacity); int* colSizes (int*)malloc(sizeof(int) * capacity); int groupCount 0; for (int i 0; i strsSize; i) { char* key makeSortedKey(strs[i]); int gid findGroup(map, key); if (gid -1) { if (groupCount capacity) { capacity * 2; result (char***)realloc(result, sizeof(char**) * capacity); colSizes (int*)realloc(colSizes, sizeof(int) * capacity); } gid groupCount; result[gid] (char**)malloc(sizeof(char*)); result[gid][0] strs[i]; colSizes[gid] 1; insertGroup(map, key, gid); } else { int newLen colSizes[gid] 1; result[gid] (char**)realloc(result[gid], sizeof(char*) * newLen); result[gid][colSizes[gid]] strs[i]; colSizes[gid] newLen; } free(key); } freeMap(map); *returnSize groupCount; *returnColumnSizes colSizes; return result; }4.2 核心代码段为什么这样写result和colSizes的初始容量是 16满了就翻倍。这是典型的动态数组扩容策略realloc会在需要时自动搬移内存翻倍扩容保证平均每次插入 O(1) 的分摊成本。为什么不用固定strsSize因为分组数量在遍历前是未知的用动态扩容可以精确匹配实际分组数也不会浪费太多内存。每组内部的char**数组用realloc按 1 个指针递增扩容。严格地说这种逐次1扩容在单组元素很多时会有一定搬运开销但本题 n 最大才 10000单组最多也就 10000 个指针直接在判题环境是没问题的。真正追求极致的人会在第六节看到“翻倍扩容”的优化思路。findGroup返回-1表示“没找到”。这个哨兵值非常安全因为分组编号从 0 开始永远不会是负数。查到已有分组时代码直接把新指针追加到该组末尾查不到时就先扩容外层数组、再创建新组并把key - gid写进哈希表。最后freeMap的顺序很讲究先取next指针再释放当前节点的key和节点本身接着才往前走。如果反过来先释放节点next就悬空了后面整条链表都会泄漏。5. 本地调试中踩过的四个坑5.1 空字符串与len等于0时的qsort最容易被忽略的是空字符串。strs里可能混入strlen()等于 0如果直接qsort(key, 0, sizeof(char), cmpChar)C 标准并没有明确规定qsort对 0 个元素的行为虽然多数实现会原样返回但严谨一点还是要加上if (len 0)的保护。另外一个和空串相关的问题是边界测试本地验证时[, ]这两个空串应该被分到同一组result[0]里有两个元素两个元素都指向空串。我第一版代码忘了单独测这个用例结果哈希函数返回 0、排序副本是空串逻辑上没问题但如果没有if (len 0)的防护某些环境下qsort会直接崩。5.2 realloc扩容时的指针安全我的示例代码里result realloc(result, ...)这种写法严格来说有一个隐患如果realloc失败它会返回 NULL 并保持原指针不变但你把 NULL 赋给result就等于弄丢了原来的内存块。力扣的判题内存很充足几乎不可能触发所以示例代码保留了这种简洁写法。工程上正确写法是这样char*** tmp (char***)realloc(result, sizeof(char**) * capacity); if (tmp ! NULL) { result tmp; } else { // 不要覆盖 result原指针还可以继续用 }colSizes同理。如果你在本地用 AddressSanitizer 跑记得同时检查这个细节。5.3 哈希表释放顺序freeMap里最容易写错的是这个顺序HashNode* next p-next; free(p-key); free(p); p next;很多人会先free(p)再去拿p-next这就是典型的悬空指针访问。链表节点释放时必须先把后继节点保存下来。另一个容易漏的是p-key。哈希表的 key 在插入时是malloc出来的独立字符串释放节点前必须单独free(p-key)否则每插入一个新键就泄漏一块内存。你可以在本地启用 AddressSanitizer 验证自己的代码有没有泄漏。5.4 三层指针返回值的理解char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes)这个签名第一眼确实吓人。我的理解方式是从右往左拆返回值最外层char***是“分组数组”的指针每个元素是一个分组每个分组是一个char**它是一个“字符串指针的数组”每个字符串是char*指向原始strs里的某个单词。所以result[gid]是第 gid 组的字符串指针数组result[gid][colSizes[gid]] strs[i]就是把当前单词指针放到第 gid 组末尾。一旦把指针层级拆清楚代码里那些[][]就不会看花眼了。6. 复杂度、性能与备选方案对比6.1 时间复杂度到底是多少精确地算一笔账设 n 是字符串个数k 是平均字符串长度。makeSortedKey对每个字符串做一次qsort耗时 O(klogk)总耗时 O(n * klogk)哈希表的查找和插入平均 O(1)但如果 key 很长strcmp需要扫完整个 key也是 O(k)结果填充里每组的realloc分摊到每个指针是 O(1)。所以整体时间复杂度是 O(n * klogk)。这个复杂度在力扣 49 题的所有主流方案里属于优秀水平。空间上哈希表里保存了 n 个 key总长 O(nk)加上桶数组 O(HASH_SIZE) 和结果指针数组 O(n)整体空间复杂度 O(nk HASH_SIZE)。6.2 计数编码和“翻倍容量”两个优化方向如果你觉得排序成本高可以把makeSortedKey替换成计数编码版本统计 26 个字母数量生成一个固定格式的字符串作为 key。生成成本从 O(klogk) 降到 O(k)但 key 变长了几十倍哈希和strcmp又会变慢。我实测在平均长度 10 到 100 的用例下两种方案耗时基本持平单词越长计数编码优势越大。建议你把两种都写了跑一遍对比体会一下“成本转移”的感觉。更值得做的优化是每组内部用翻倍扩容代替逐次1int newCap groupCap[gid] * 2; char** tmp (char**)realloc(result[gid], sizeof(char*) * newCap);这样单组从 1 涨到 10000 只需要大约 14 次 realloc而不是 9999 次对极端数据有明显改善。只是代码里要新增一组groupCap数组逻辑略复杂。力扣 49 的数据规模不大不做也能过但理解这个优化对你以后处理更大规模数据有帮助。6.3 这道题真正教会我的用 C 刷这种“字典类”题目最大的收获不是记住某段模板而是真正理解哈希表为什么存在它把“按键查找”从 O(n) 降到了平均 O(1)。在高级语言里写一行HashMap其实是对底层结构的封装。自己从头写一次才会明白为什么哈希函数要选质数、为什么用链地址法、为什么 key 必须是不可变的拷贝。这些认知不绑定特定语言面试时候手写哈希表也很加分。最后分享一个小体会我后来把这段代码里的哈希函数、链表释放、动态扩容单独抽成了通用模块其它需要“字符串映射到整数”的题目直接复用。力扣上一旦遇到 C 语言的手写哈希表题有这一套兜底心里基本就有底了。
