本文旨在探讨如何高效统计字符串中唯一字符的个数。虽然理论上的时间复杂度下限为 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)，但在某些特定情况下，我们可以通过使用固定大小的数组来优化内存使用。
适用场景：
- 字符串中的字符集是有限且已知的，例如 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 是一种通用的解决方案，具有良好的时间和空间复杂度。在字符集有限且已知的情况下，可以使用固定大小的数组来优化内存使用。选择哪种方法取决于具体的应用场景和对时间和空间复杂度的要求。在实际应用中，需要根据具体情况进行权衡，选择最合适的解决方案。
评论（已关闭）
评论已关闭