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

本文旨在探讨如何高效计算给定字符串中唯一字符的数量。针对此问题，虽然理论上的时间复杂度下限为 O(n)，但可以通过优化数据结构的选择和算法实现，在特定场景下降低内存占用，提升实际性能。本文将详细介绍使用哈希集合（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("Unique characters count: " + uniqueCount); // Output: 4     } }

代码解析：

1. 创建 HashSet: 首先，创建一个 HashSet 对象，用于存储字符串中的唯一字符。
2. 遍历字符串: 遍历输入字符串 s 的每一个字符。
3. 添加字符到 HashSet: 对于每个字符，使用 uniqueChars.add(s.charAt(i)) 将其添加到 HashSet 中。HashSet 会自动忽略重复的字符。
4. 返回 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     } }

代码解析：

1. 创建计数数组: 创建一个长度为 256 的整型数组 charCounts，用于存储每个 ASCII 字符出现的次数。
2. 统计字符出现次数: 遍历字符串 s，对于每个字符，将其 ASCII 码作为索引，在 charCounts 数组中对应的位置加 1。
3. 统计非零元素个数: 遍历 charCounts 数组，统计其中非零元素的个数，即为唯一字符的数量。

时间复杂度： 该算法的时间复杂度仍然为 O(n)，其中 n 是字符串的长度。虽然需要遍历数组，但数组长度是固定的（256），因此遍历数组的时间复杂度可以认为是 O(1)。

空间复杂度： 该算法的空间复杂度为 O(1)，因为计数数组的大小是固定的，与字符串的长度无关。

注意事项：

• 这种方法只适用于字符集有限制的情况。如果字符集很大，例如包含 Unicode 字符，则需要创建更大的数组，这可能会导致内存浪费。
• 使用 HashSet 的方法更通用，适用于任何字符集。

总结

虽然两种方法的时间复杂度都是 O(n)，但在特定情况下，基于数组计数的方法可以降低内存占用。选择哪种方法取决于具体的应用场景和对内存使用的要求。在实际开发中，应该根据实际情况进行权衡，选择最适合的方法。通常来说，使用 HashSet 的方法更通用，也更易于理解和维护。只有在对内存有严格限制，且字符集已知且较小的情况下，才考虑使用数组计数的方法。