本文旨在探讨如何高效计算给定字符串中唯一字符的数量。针对此问题，虽然理论上的时间复杂度下限为 O(n)，但可以通过优化数据结构的选择和算法实现，在特定场景下降低内存占用，提升实际性能。本文将详细介绍使用哈希集合（HashSet）的常规方法，并提出一种基于数组计数的方法，分析其优缺点及适用场景。
使用 HashSet 计算唯一字符数
最直接且常用的方法是使用 HashSet。HashSet 是一种不允许重复元素的集合，利用其特性可以方便地统计字符串中唯一字符的数量。
以下是 Java 代码示例：
import java.util.HashSet;
public class UniqueCharacters {
public static int countUniqueCharacters(String s) {
HashSet 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("Unique characters count: " + uniqueCount); // Output: 4
}
} 代码解析：
-
创建 HashSet: 首先，创建一个 HashSet
对象，用于存储字符串中的唯一字符。 - 遍历字符串: 遍历输入字符串 s 的每一个字符。
- 添加字符到 HashSet: 对于每个字符，使用 uniqueChars.add(s.charAt(i)) 将其添加到 HashSet 中。HashSet 会自动忽略重复的字符。
- 返回 HashSet 大小: 循环结束后，HashSet 中存储的就是字符串中所有唯一的字符，调用 uniqueChars.size() 方法返回 HashSet 的大小，即唯一字符的数量。
时间复杂度： 该算法的时间复杂度为 O(n)，其中 n 是字符串的长度。因为需要遍历字符串一次，并且 HashSet 的 add 操作的平均时间复杂度为 O(1)。
空间复杂度： 该算法的空间复杂度为 O(k)，其中 k 是字符串中唯一字符的数量。因为需要使用 HashSet 存储这些唯一字符。
基于数组计数的优化方法
在某些特定情况下，例如当字符串中的字符集有限制时（例如，只包含 ASCII 字符），可以使用数组计数的方法来优化内存使用。
以下是 Java 代码示例：
public class UniqueCharacters {
public static int countUniqueCharactersAscii(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
int[] charCounts = new int[256]; // Assuming ASCII characters
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 = countUniqueCharactersAscii(str);
System.out.println("Unique characters count: " + uniqueCount); // Output: 4
}
}代码解析：
- 创建计数数组: 创建一个长度为 256 的整型数组 charCounts，用于存储每个 ASCII 字符出现的次数。
- 统计字符出现次数: 遍历字符串 s，对于每个字符，将其 ASCII 码作为索引，在 charCounts 数组中对应的位置加 1。
- 统计非零元素个数: 遍历 charCounts 数组，统计其中非零元素的个数，即为唯一字符的数量。
时间复杂度： 该算法的时间复杂度仍然为 O(n)，其中 n 是字符串的长度。虽然需要遍历数组，但数组长度是固定的（256），因此遍历数组的时间复杂度可以认为是 O(1)。
空间复杂度： 该算法的空间复杂度为 O(1)，因为计数数组的大小是固定的，与字符串的长度无关。
注意事项：
- 这种方法只适用于字符集有限制的情况。如果字符集很大，例如包含 Unicode 字符，则需要创建更大的数组，这可能会导致内存浪费。
- 使用 HashSet 的方法更通用，适用于任何字符集。
总结
虽然两种方法的时间复杂度都是 O(n)，但在特定情况下，基于数组计数的方法可以降低内存占用。选择哪种方法取决于具体的应用场景和对内存使用的要求。在实际开发中，应该根据实际情况进行权衡，选择最适合的方法。通常来说，使用 HashSet 的方法更通用，也更易于理解和维护。只有在对内存有严格限制，且字符集已知且较小的情况下，才考虑使用数组计数的方法。
