如何在JavaScript中以O(n)时间复杂度返回相同字母元素？

嘿，我来帮你把这个分组问题优化到更高效的时间复杂度！你的需求是把数组里由相同字母组成的字符串分组，原来用嵌套循环的方式确实会在数组变大的时候变得很慢——毕竟两两对比的O(n²)复杂度，数据量上去之后性能会雪崩。

问题分析 #

原来的思路里，你用isSameChars函数对比两个字符串，但嵌套循环意味着每个字符串都要和其他所有字符串对比一次，每次对比还要做两次排序（O(k log k)，k是字符串长度），整体时间复杂度是O(n²k log k)，这显然不是最优解。

优化思路：用哈希表做分组 #

核心想法是：给每个同字母组找一个唯一的“标识”，用这个标识作为键，把对应的字符串都放到同一个数组里。这样只需要遍历一次原数组，就能完成分组，时间复杂度直接降下来。

有两种常用的标识生成方式：

方式1：排序后的字符串作为标识（简单易实现）

把每个字符串的字符排序后得到的结果，就是同字母组的唯一标识——比如dog和ogd排序后都是dgo，自然会被分到同一组。

代码实现：

const groupAnagrams = (arr) => {
  const groupMap = new Map();
  
  for (const str of arr) {
    // 生成当前字符串的排序标识
    const sortedKey = str.split('').sort().join('');
    
    // 把字符串加到对应分组里
    if (groupMap.has(sortedKey)) {
      groupMap.get(sortedKey).push(str);
    } else {
      groupMap.set(sortedKey, [str]);
    }
  }
  
  // 把Map里的分组转成数组返回
  return Array.from(groupMap.values());
};

// 测试示例
const arr = ['dog', 'come', 'ogd', 'something', 'emoc'];
console.log(groupAnagrams(arr)); 
// 输出：[ ['dog', 'ogd'], ['come', 'emoc'], ['something'] ]

这个方案的时间复杂度是O(nk log k)：遍历数组是O(n)，每个字符串排序是O(k log k)，比原来的O(n²)高效太多，而且代码非常简洁。

方式2：字符计数作为标识（极致性能，O(nk)复杂度）

如果字符串很长，排序的成本会变高，这时候可以用字符出现的次数作为标识——比如统计每个字符串里a到z的出现次数，转成一个字符串（比如"1,0,0,...2,..."），这样不需要排序，只需要遍历每个字符串一次。

代码实现：

const groupAnagrams = (arr) => {
  const groupMap = new Map();
  
  for (const str of arr) {
    // 初始化26个字母的计数数组（a-z对应索引0-25）
    const charCount = new Array(26).fill(0);
    
    // 统计每个字符的出现次数
    for (const char of str) {
      const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
      charCount[charIndex]++;
    }
    
    // 把计数数组转成字符串作为唯一标识
    const countKey = charCount.join(',');
    
    // 分组逻辑和之前一致
    if (groupMap.has(countKey)) {
      groupMap.get(countKey).push(str);
    } else {
      groupMap.set(countKey, [str]);
    }
  }
  
  return Array.from(groupMap.values());
};

这个方案的时间复杂度是O(nk)，是线性相关的复杂度，在处理大规模数据或者超长字符串时，性能会比排序方案更好。

为什么这两种方案比嵌套循环好？ #

原来的嵌套循环会做大量重复工作：比如dog和ogd对比一次，ogd和dog又会对比一次，完全是冗余操作。而哈希表分组只需要处理每个字符串一次，直接把它们归到对应的组里，没有任何重复计算。

内容的提问来源于stack exchange，提问作者hackrack