统计字符串中唯一字符个数：优化时间复杂度-java教程-PHP中文网

统计字符串中唯一字符个数：优化时间复杂度

霞舞

发布： 2025-08-12 22:24:17

原创

302人浏览过

统计字符串中唯一字符个数：优化时间复杂度

本文旨在探讨如何高效统计字符串中唯一字符的个数。虽然理论上的时间复杂度下限为 O(n)，但通过合理选择数据结构，可以优化内存使用并提升实际性能。本文将分析基于 HashSet 的常见方法，并介绍使用固定大小数组的优化策略，最后讨论其适用场景和局限性。

使用 HashSet 统计唯一字符

一种常见的解决方案是使用 HashSet 来存储字符串中的每个字符。由于 HashSet 具有自动去重的特性，因此最终 HashSet 中元素的个数即为字符串中唯一字符的个数。

以下是 Java 代码示例：

import java.util.HashSet;

public class UniqueCharacters {

    public static int countUniqueCharacters(String s) {
        HashSet<Character> uniqueChars = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            uniqueChars.add(s.charAt(i));
        }
        return uniqueChars.size();
    }

    public static void main(String[] args) {
        String str = "abcaabbd";
        int uniqueCount = countUniqueCharacters(str);
        System.out.println("字符串 \"" + str + "\" 中唯一字符的个数为: " + uniqueCount); // 输出: 4
    }
}

登录后复制

这段代码的时间复杂度为 O(n)，其中 n 是字符串的长度。这是因为我们需要遍历字符串中的每个字符，并且 HashSet 的 add() 操作的平均时间复杂度为 O(1)。空间复杂度取决于字符串中唯一字符的数量，最坏情况下为 O(n)，即字符串中所有字符都是唯一的。

使用固定大小数组优化

虽然使用 HashSet 的方法在时间复杂度上已经达到了最优的 O(n)，但在某些特定情况下，我们可以通过使用固定大小的数组来优化内存使用。

适用场景：

怪兽AI数字人

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

查看详情

字符串中的字符集是有限且已知的，例如 ASCII 字符集（256个字符）。

实现思路：

创建一个长度为字符集大小的数组（例如，对于 ASCII 字符集，数组长度为 256）。
遍历字符串，将每个字符对应的数组元素的值加 1。字符的 ASCII 码值可以用作数组的索引。
遍历数组，统计非零元素的个数，即为字符串中唯一字符的个数。

以下是 Java 代码示例：

public class UniqueCharactersOptimized {

    public static int countUniqueCharactersOptimized(String s) {
        int[] charCounts = new int[256]; // 假设使用 ASCII 字符集
        for (int i = 0; i < s.length(); i++) {
            charCounts[s.charAt(i)]++;
        }

        int uniqueCount = 0;
        for (int count : charCounts) {
            if (count > 0) {
                uniqueCount++;
            }
        }
        return uniqueCount;
    }

    public static void main(String[] args) {
        String str = "abcaabbd";
        int uniqueCount = countUniqueCharactersOptimized(str);
        System.out.println("字符串 \"" + str + "\" 中唯一字符的个数为: " + uniqueCount); // 输出: 4
    }
}

登录后复制

这段代码的时间复杂度仍然是 O(n)，其中 n 是字符串的长度。但是，空间复杂度降低到了 O(1)，因为数组的大小是固定的，与字符串的长度无关。

注意事项：

这种方法只适用于字符集有限且已知的情况。如果字符集很大或者未知，则不适用。
在使用这种方法时，需要确保字符串中的字符都在字符集范围内。否则，可能会导致数组越界错误。

总结

统计字符串中唯一字符的个数是一个常见的编程问题。使用 HashSet 是一种通用的解决方案，具有良好的时间和空间复杂度。在字符集有限且已知的情况下，可以使用固定大小的数组来优化内存使用。选择哪种方法取决于具体的应用场景和对时间和空间复杂度的要求。在实际应用中，需要根据具体情况进行权衡，选择最合适的解决方案。

以上就是统计字符串中唯一字符个数：优化时间复杂度的详细内容，更多请关注php中文网其它相关文章！