Java实现无排序分组同字母异位词：哈希映射与字符计数详解-java教程-PHP中文网

Java实现无排序分组同字母异位词：哈希映射与字符计数详解

本文详细阐述了一种在java中高效分组同字母异位词的方法，该方法通过利用字符频率计数数组作为哈希映射的键，避免了对字符串进行排序，从而优化了性能。文章深入探讨了字符频率数组如何作为唯一标识符，并提供了具体的代码实现、详细的时间复杂度分析以及相关注意事项，旨在为开发者提供一个清晰且专业的教程。

引言

在编程挑战中，分组同字母异位词（Group Anagrams）是一个常见问题。同字母异位词是指由相同字母但顺序不同的字符串组成，例如 "eat"、"tea" 和 "ate" 都是同字母异位词。解决这类问题的一个直观方法是对每个字符串进行排序，然后将排序后的字符串作为哈希表的键。然而，这种方法的时间复杂度通常较高，因为它涉及到对每个字符串进行排序操作。本文将介绍一种更高效的无排序方法，通过字符频率计数来为同字母异位词生成唯一的哈希键。

核心思想：字符频率计数作为哈希键

同字母异位词的本质在于它们拥有相同的字符集合和每个字符的相同出现次数。例如，"listen" 和 "silent" 都包含一个 'l'、一个 'i'、一个 's'、一个 't'、一个 'e' 和一个 'n'。基于这一特性，我们可以创建一个“签名”来唯一标识一组同字母异位词，而无需对字符串本身进行排序。

这个“签名”就是字符频率计数数组。对于只包含小写英文字母的字符串，我们可以使用一个长度为 26 的整型数组来记录每个字母的出现次数。数组的每个索引对应一个字母（例如，索引 0 对应 'a'，索引 1 对应 'b'，以此类推），存储该字母在字符串中出现的次数。

例如，对于字符串 "eat"：

立即学习“Java免费学习笔记（深入）”；

'e' 出现 1 次
'a' 出现 1 次
't' 出现 1 次
其他字母出现 0 次

对应的频率数组将是 [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]（其中第0位是'a'，第4位是'e'，第19位是't'）。所有与 "eat" 是同字母异位词的字符串，如 "tea" 和 "ate"，都会生成完全相同的频率数组。

实现细节：从频率数组到哈希键

为了将这个频率数组用作 HashMap 的键，我们需要将其转换为一个不可变的、可哈希的对象，最常见且方便的方式是将其转换为 String 类型。Java 的 Arrays.toString(int[] a) 方法可以将一个整型数组转换为其字符串表示形式，例如 [1, 0, 0, ..., 1]。这个字符串表示形式将作为 HashMap 的键，而其值则是一个 List<String>，用于存储所有具有相同频率数组（即同字母异位词）的原始字符串。

怪兽AI数字人

数字人短视频创作，数字人直播，实时驱动数字人

查看详情

算法步骤：

初始化: 创建一个 HashMap<String, List<String>> 来存储分组结果。键是字符频率数组的字符串表示，值是对应的同字母异位词列表。
遍历字符串数组: 迭代输入字符串数组中的每个字符串。
构建频率数组: 对于每个字符串，创建一个长度为 26 的 int 数组 input，并遍历字符串中的每个字符：
- 通过 str.charAt(i) - 'a' 计算字符在字母表中的偏移量，将其作为 input 数组的索引。
- 将 input[index] 的值递增，记录该字符的出现次数。
生成哈希键: 使用 Arrays.toString(input) 将频率数组转换为一个 String 类型的键 inputStr。
哈希映射操作:
- 检查 outputMap 是否已包含 inputStr 作为键。
- 如果存在，说明已经发现了一组同字母异位词，将当前字符串添加到 outputMap.get(inputStr) 对应的列表中。
- 如果不存在，则创建一个新的 ArrayList<String>，将当前字符串添加进去，然后将 inputStr 作为键，新创建的列表作为值，存入 outputMap。
收集结果: 遍历 outputMap 的所有值（即所有的 List<String>），将它们添加到一个新的 List<List<String>> 中作为最终结果返回。

代码示例

以下是基于上述思想的 Java 实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramGrouper {

    /**
     * 将一组字符串中的同字母异位词进行分组。
     *
     * @param strs 待分组的字符串数组。
     * @return 包含同字母异位词分组的列表。
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        // 最终结果列表
        List<List<String>> output = new ArrayList<>();
        // 处理空输入情况
        if (strs == null || strs.length == 0) {
            return output;
        }

        // 使用 HashMap 存储分组结果
        // 键：字符频率数组的字符串表示 (e.g., "[1, 0, ..., 1]")
        // 值：包含所有对应同字母异位词的列表
        Map<String, List<String>> outputMap = new HashMap<>();

        // 遍历输入字符串数组
        for (String str : strs) {
            // 创建一个长度为 26 的数组，用于记录每个小写字母的出现次数
            // 索引 0 -> 'a', 索引 1 -> 'b', ..., 索引 25 -> 'z'
            int[] charCounts = new int[26];
            // 遍历当前字符串的每个字符，更新 charCounts 数组
            for (int i = 0; i < str.length(); i++) {
                charCounts[str.charAt(i) - 'a']++;
            }

            // 将字符频率数组转换为字符串，作为 HashMap 的键
            // 例如，对于 "eat"，charCounts 可能是 [1,0,0,0,1,...,1]，
            // Arrays.toString() 会将其转换为 "[1, 0, 0, 0, 1, 0, ..., 1, 0, 0, 0, 0, 0, 0]"
            String key = Arrays.toString(charCounts);

            // 检查 HashMap 中是否已存在该键
            if (outputMap.containsKey(key)) {
                // 如果存在，说明找到了一个同字母异位词，将其添加到对应的列表中
                outputMap.get(key).add(str);
            } else {
                // 如果不存在，创建一个新的列表，将当前字符串添加进去，并将其作为新的键值对存入 HashMap
                List<String> newList = new ArrayList<>();
                newList.add(str);
                outputMap.put(key, newList);
            }
        }

        // 将 HashMap 中所有的值（即所有的同字母异位词列表）收集到最终结果列表中
        output.addAll(outputMap.values());
        return output;
    }

    public static void main(String[] args) {
        AnagramGrouper grouper = new AnagramGrouper();
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result1 = grouper.groupAnagrams(strs1);
        System.out.println("示例 1 分组结果: " + result1);
        // 预期输出可能为: [[bat], [nat, tan], [ate, eat, tea]] 或类似顺序

        String[] strs2 = {""};
        List<List<String>> result2 = grouper.groupAnagrams(strs2);
        System.out.println("示例 2 分组结果: " + result2); // 预期输出: [[]]

        String[] strs3 = {"a"};
        List<List<String>> result3 = grouper.groupAnagrams(strs3);
        System.out.println("示例 3 分组结果: " + result3); // 预期输出: [[a]]
    }
}

登录后复制

时间复杂度分析

该算法的时间复杂度主要由两个嵌套循环决定：

外层循环: 遍历输入字符串数组 strs，假设数组中有 m 个字符串。
内层循环: 对于每个字符串 str，遍历其所有字符以构建频率计数数组。假设字符串的平均长度为 n。

具体操作及复杂度：

初始化 charCounts 数组: new int[26] 是 O(1) 操作。
构建 charCounts 数组: 对于每个字符串，需要遍历其 n 个字符。每个字符的访问和数组更新是 O(1) 操作。因此，这一步的复杂度是 O(n)。
Arrays.toString(charCounts): 将长度为 26 的数组转换为字符串。这可以看作是 O(1) 操作（因为它总是处理固定大小的数组）。
HashMap 操作 (containsKey, get, put): 在理想情况下（哈希冲突较少），这些操作的平均时间复杂度是 O(1)。

综合计算：

外层循环执行 m 次。
在每次外层循环中：
- 构建 charCounts 数组：O(n)
- Arrays.toString()：O(1)
- HashMap 操作：O(1) (平均)
- List.add()：O(1) (平均)

因此，总的时间复杂度为 m * (n + 1 + 1 + 1)，简化后为 m * (n + 3)。去除常数项后，最终的时间复杂度为 *O(m n)**。

与传统的排序方法（通常为 O(m * n log n)）相比，这种基于字符频率计数的方法在字符串长度较大时具有显著的性能优势。

空间复杂度分析

outputMap: 在最坏情况下，所有字符串都不是同字母异位词，outputMap 将存储 m 个键值对。每个键是长度为 26 的数组的字符串表示（固定长度），每个值是一个 List<String>，其中包含原始字符串。因此，存储所有原始字符串所需的空间是 O(m * n)（m 个字符串，平均长度 n），存储键所需的额外空间是 O(m * 26)，可以简化为 O(m)。
output 列表: 最终结果列表也存储了所有 m 个字符串，所以空间复杂度为 O(m * n)。

综合来看，空间复杂度为 *O(m n)**。

注意事项与优化

字符集限制: 当前实现假定输入字符串只包含小写英文字母。如果字符串可能包含大写字母、数字或特殊字符，或者更广泛的 Unicode 字符，则需要调整 charCounts 数组的大小（例如，使用 256 或更大的数组，或者使用 HashMap<Character, Integer> 来计数）。
键的生成: Arrays.toString() 方法是生成键的一种简洁方式。另一种方法是手动构建一个字符串，例如使用 StringBuilder 将每个字符的计数及其对应的字符拼接起来（如 "a1e1t1"），但这会稍微增加复杂性，且 Arrays.toString() 通常已足够高效。
空字符串处理: 示例代码中包含了对空字符串数组和单个空字符串的处理，它们会被正确分组。
性能对比: 尽管 O(m n) 优于 O(m n log n)，但对于非常短的字符串，排序方法的常数因子可能较小，实际性能差异可能不明显。然而，对于大多数实际场景，频率计数方法在渐近性能上更优。