【力扣刷题】49字母异位词分组，不用哈希，c语言实现

在已排序的结构体数组中，双指针通过定位相同特征码的边界实现分组。以下是详细的分步解释：

---

一、数据预处理后的结构

假设输入为 ["eat","tea","tan","ate","nat","bat"]，预处理后的结构体数组排序后如下：

原词	排序后的特征码
bat	abt
eat	aet
tea	aet
ate	aet
tan	ant
nat	ant

排序后按特征码字典序排列，相同异位词必然连续出现。

---

二、双指针分组核心逻辑

步骤分解

1. 初始化指针

   int i = 0; // 外层指针，标记当前组的起始位置
   while (i < strsSize) {int j = i; // 内层指针，探索当前组的结束位置
   

2. 内层循环定位组边界

   while (j < strsSize && strcmp(words[i].sorted, words[j].sorted) == 0) {j++;
   }
   

   • 比较 words[i].sorted 和 words[j].sorted
   • 只要特征码相同，j 就向右移动，直到遇到不同的特征码或数组末尾。

3. 截取当前组数据

   // 当前组元素数量：j - i
   char** group = malloc((j - i) * sizeof(char*));
   for (int k = i; k < j; k++) {group[k - i] = words[k].original; // 复制原词
   }
   

4. 保存分组结果

   (*returnSize)++;
   result = realloc(result, (*returnSize) * sizeof(char**));
   (*returnColumnSizes) = realloc(*returnColumnSizes, (*returnSize) * sizeof(int));
   result[*returnSize - 1] = group;
   (*returnColumnSizes)[*returnSize - 1] = j - i;
   

5. 移动外层指针

   i = j; // i 跳转到下一组的起始位置
   

---

三、动态演示

以示例数据执行过程如下：

1. 初始状态

   i=0, j=0
   words[0].sorted = "abt"
   

2. 第一组检测

   • j 从 0 开始，发现 words[0].sorted 与后续不同（“abt” vs “aet”）
   • 组范围：i=0 → j=1（包含元素 0）
   • 生成分组 ["bat"]

3. 第二组检测

   • i=1, j 从 1 开始，连续匹配 “aet”
   • 遍历到索引 3 时，words[3].sorted 仍为 “aet”
   • 当 j=4 时，发现特征码变为 “ant”
   • 组范围：i=1 → j=4（包含元素 1-3）
   • 生成分组 ["eat","tea","ate"]

4. 后续处理

   • 同理处理 “ant” 分组（i=4 → j=6）和 “abt”（最后一组）

---

四、关键优势

1. 时间复杂度优化

   • 排序后只需一次线性遍历即可完成分组，时间复杂度 O(n)。
   • 若使用哈希表（C需自行实现），哈希冲突处理会增加复杂度。

2. 内存效率

   • 原地操作已排序数组，无需额外存储哈希表。
   • 仅需保存分组指针，空间复杂度 O(n)。

---

五、边界处理

1. 空输入
   在函数开头检查 strsSize == 0，直接返回空结果。

2. 单元素情况

   if (j == i + 1) {// 单独成组
   }
   

3. 内存释放

   • 分组完成后释放 words 中的 sorted 字符串。
   • 结果数组由调用者负责释放（代码未展示）。

---

通过双指针法，代码在保证效率的同时，逻辑清晰且易于实现，是处理有序序列分组的经典模式。

以下是使用 C 语言实现的字母异位词分组代码，结合了排序和双指针技术：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 比较字符用于排序
int compare_char(const void* a, const void* b) {return (*(char*)a - *(char*)b);
}// 单词结构体保存原词和排序后的词
typedef struct {char* original;char* sorted;
} Word;// 比较单词结构体用于分组
int compare_word(const void* a, const void* b) {return strcmp(((Word*)a)->sorted, ((Word*)b)->sorted);
}char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {if (strsSize == 0) {*returnSize = 0;return NULL;}// 1. 创建单词结构体数组Word* words = malloc(strsSize * sizeof(Word));for (int i = 0; i < strsSize; i++) {words[i].original = strs[i];words[i].sorted = strdup(strs[i]);qsort(words[i].sorted, strlen(words[i].sorted), 1, compare_char);}// 2. 对结构体数组排序qsort(words, strsSize, sizeof(Word), compare_word);// 3. 双指针法分组char*** result = NULL;*returnSize = 0;*returnColumnSizes = NULL;int i = 0;while (i < strsSize) {int j = i;while (j < strsSize && !strcmp(words[i].sorted, words[j].sorted)) j++;// 创建分组char** group = malloc((j-i) * sizeof(char*));for (int k = i; k < j; k++) {group[k-i] = words[k].original;}// 更新结果集(*returnSize)++;result = realloc(result, (*returnSize)*sizeof(char**));(*returnColumnSizes) = realloc(*returnColumnSizes, (*returnSize)*sizeof(int));result[*returnSize-1] = group;(*returnColumnSizes)[*returnSize-1] = j-i;i = j;}// 释放中间资源for (int i = 0; i < strsSize; i++) free(words[i].sorted);free(words);return result;
}

算法思路

1. 预处理排序
   为每个单词生成排序后的版本作为特征码：

   "eat" → "aet"
   "tea" → "aet"
   

2. 结构体排序
   将所有单词及其特征码存入结构体数组，并按特征码排序：

   [{"bat", "abt"},{"eat", "aet"}, {"tea", "aet"},{"tan", "ant"},...
   ]
   

3. 双指针分组
   遍历排序后的结构体数组，用双指针找到每组边界：

   i=0 → j=1（特征码不同）
   分组1: ["bat"]
   i=1 → j=4（特征码相同）
   分组2: ["eat","tea","ate"]
   

复杂度分析

• 时间复杂度：

  • 预处理排序：O(n*klogk)，n 为单词数，k 为单词最大长度
  • 结构体排序：O(n log n)
  • 总复杂度：O(nklogk + n log n)

• 空间复杂度：O(nk)，用于存储排序后的特征码

关键点

1. 特征码生成
   通过排序将异位词统一为相同形式，便于分组识别。

2. 双指针分组
   利用排序后的有序性，快速定位每组边界。

3. 动态内存管理
   使用 realloc 动态扩展结果数组，适应任意数量的分组。

该实现充分利用 C 语言的底层特性，在无内置哈希表的情况下，通过排序和双指针实现高效分组。