LeetCode无排序分组变位词：基于字符频率的Java实现与复杂度分析-java教程-PHP中文网

LeetCode无排序分组变位词：基于字符频率的Java实现与复杂度分析

DDD

发布： 2025-10-14 12:32:22

原创

856人浏览过

LeetCode无排序分组变位词：基于字符频率的Java实现与复杂度分析

本文详细探讨了一种在leetcode中无需排序即可对字符串数组进行变位词分组的java解决方案。该方法巧妙地利用字符频率数组作为hashmap的键，将具有相同字符组成（即变位词）的字符串高效地归类。文章深入解析了`arrays.tostring()`在此过程中的关键作用，并提供了详细的代码实现及严谨的时间复杂度`o(m*n)`分析，其中`m`为字符串数量，`n`为平均字符串长度。

变位词分组的核心思想

变位词（Anagrams）是指由相同字母以不同顺序排列而成的单词或短语，例如 "eat", "tea", "ate" 都是彼此的变位词。传统的变位词判断方法通常涉及对字符串进行排序，然后比较排序后的结果。然而，这种方法对于每个字符串都需要O(N log N)的时间复杂度。为了优化性能，我们可以采用一种无需排序的方法：字符频率计数。

其核心思想是：如果两个字符串是变位词，那么它们包含的每个字符的数量必然是相同的。例如，"eat" 和 "tea" 都包含一个 'e'，一个 'a'，一个 't'。因此，我们可以为每个字符串构建一个字符频率“指纹”，并使用这个指纹作为哈希表的键来将变位词分组。

基于字符频率数组的实现

在Java中，我们可以使用一个长度为26的整型数组来记录每个小写英文字母的出现次数。数组的每个索引对应一个字母（0对应'a'，1对应'b'，以此类推）。

构建频率数组：对于输入数组中的每个字符串str，初始化一个int[26]的数组input。遍历str中的每个字符c，通过input[c - 'a']++来增加对应字符的计数。例如，对于字符串 "eat"：
- input['e' - 'a'] 增加 1
- input['a' - 'a'] 增加 1
- input['t' - 'a'] 增加 1 最终，input 数组可能看起来像 [1, 0, 0, 0, 1, 0, ..., 1, ..., 0]，其中 'a', 'e', 't' 对应的位置是 1，其余为 0。
生成哈希键：关键在于如何将这个int[26]数组转换为一个可以作为HashMap键的唯一标识。Arrays.toString(input) 方法在此发挥了巧妙的作用。它会将整型数组转换成一个字符串表示，例如 "[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]"。这个字符串是唯一且一致的，因为：
- 任何变位词（如 "eat", "tea", "ate"）都会生成完全相同的字符频率数组。
- Arrays.toString() 会将相同的数组内容转换成相同的字符串。因此，这个字符串就成为了变位词组的理想哈希键。
分组存储：使用一个HashMap<String, List<String>>来存储分组结果。键是上述生成的频率数组字符串，值是一个List<String>，包含所有具有该频率模式的原始字符串。

立即学习“Java免费学习笔记（深入）”；
- 如果outputMap中已存在该频率字符串作为键，则将当前字符串添加到对应的List中。
- 如果不存在，则创建一个新的List，将当前字符串添加进去，并将该频率字符串作为键，新List作为值存入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 {

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> output = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return output;
        }

        Map<String, List<String>> outputMap = new HashMap<>();

        for (String str : strs) {
            // 1. 构建字符频率数组
            int[] charCounts = new int[26]; // 26个小写英文字母
            for (char c : str.toCharArray()) {
                charCounts[c - 'a']++;
            }

            // 2. 将频率数组转换为字符串作为HashMap的键
            String frequencyKey = Arrays.toString(charCounts);

            // 3. 根据键进行分组存储
            if (outputMap.containsKey(frequencyKey)) {
                outputMap.get(frequencyKey).add(str);
            } else {
                List<String> anagramList = new ArrayList<>();
                anagramList.add(str);
                outputMap.put(frequencyKey, anagramList);
            }
        }

        // 4. 收集所有分组结果
        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], [eat, tea, ate]] (顺序可能不同)

        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]]
    }
}

登录后复制

时间复杂度分析

该算法的时间复杂度可以按以下步骤进行分析：

百度GBI

百度GBI-你的大模型商业分析助手

104

查看详情

外层循环：遍历输入字符串数组strs，假设数组中有m个字符串。这一步的复杂度是O(m)。
内层循环（字符计数）：对于每个字符串str，我们都需要遍历其所有字符来构建频率数组。假设字符串的平均长度为n。那么，对于每个字符串，此操作的复杂度是O(n)。
Arrays.toString()：将长度为26的int数组转换为字符串。由于数组长度是固定的常数26，此操作的复杂度是O(1)（或者更精确地说，O(26)，可以简化为O(1)）。
HashMap操作：containsKey(), get(), put(), add()等操作在平均情况下都具有O(1)的时间复杂度。在最坏情况下（哈希冲突严重），可能退化到O(k)，其中k是键的长度。在这里，我们的键是一个字符串，其长度也是固定的常数（Arrays.toString()生成的字符串长度固定，与26个字符的数组相关）。因此，这些操作可以视为O(1)。

综合以上分析，总时间复杂度为：

外层循环执行m次。
每次外层循环中，执行O(n)的字符计数操作。
每次外层循环中，执行O(1)的Arrays.toString()操作。
每次外层循环中，执行O(1)的HashMap和ArrayList操作。

因此，总时间复杂度可以表示为 m * (n + 1 + 1)，即 O(m * n + 2m)。当m和n足够大时，常数项和较低次项可以忽略，最终的时间复杂度为 *`O(m n)`**。

注意事项与总结

字符集限制：此方案假设输入字符串只包含小写英文字母。如果包含大写字母、数字或其他字符，需要调整频率数组的大小（例如，使用128或256来覆盖ASCII码）或使用HashMap<Character, Integer>来存储频率。
空间复杂度：空间复杂度主要取决于HashMap存储的键值对数量。最坏情况下，所有字符串都不是变位词，HashMap会存储m个键，每个键是一个字符串（长度固定），每个值是一个List<String>。因此，空间复杂度为O(m * k)，其中k是键的长度，可以简化为O(m)。此外，每个List<String>会存储原始字符串，因此还需要O(总字符数)的空间。
性能优势：相较于对每个字符串进行排序的方法，这种基于频率计数的方法避免了对字符串内部进行比较排序的O(N log N)开销，在许多情况下能够提供更好的性能。

通过巧妙地利用字符频率数组和Arrays.toString()方法，我们能够高效地解决变位词分组问题，为处理大量字符串数据提供了一个优化方案。

以上就是LeetCode无排序分组变位词：基于字符频率的Java实现与复杂度分析的详细内容，更多请关注php中文网其它相关文章！