打印字符串中的所有不同字符

引言

在计算机编程领域，字符串操作是基本任务之一。无论是解析用户输入、处理文本数据还是分析模式，处理字符串都是不可避免的。一个常见的问题是从给定字符串中提取不同的字符。

理解问题

在深入研究解决方案之前，我们先阐明问题陈述。给定一个字符串，我们的任务是提取并打印其中存在的所有不同字符。例如，如果输入字符串是“hello”，则不同字符将是“h”、“e”、“l”和“o”。

方法 1：使用数组计数出现次数

一个简单的方法是使用数组来计算字符串中每个字符的出现次数。

步骤：

• 创建一个数组来存储每个字符的计数。由于 ASCII 字符范围从 0 到 255，我们可以使用大小为 256 的数组。
• 遍历字符串并增加每个遇到的字符的计数。
• 最后，迭代数组并打印计数大于零的字符。

实施

说明

• printDistinctChars 函数被定义为接收字符串 (str) 的常量引用作为其参数，并返回 void，这意味着它不返回任何值。此函数负责计数和打印输入字符串中不同的字符。
• 在 printDistinctChars 内部，声明了一个整数常量 CHAR_COUNT，其值为 256，假设是 ASCII 字符。此常量表示 ASCII 字符集中可能的字符数。
• 一个大小为 CHAR_COUNT 的整数数组 freq 被初始化为零。此数组用于存储输入字符串中遇到的每个字符的频率。
• 然后，该函数使用基于范围的 for 循环遍历输入字符串中的每个字符 ch。对于遇到的每个字符，都会增加 freq 数组中对应的频率。
• 在计算输入字符串中每个字符的频率后，该函数遍历 freq 数组以打印频率不为零的字符。
• 在循环内部，如果数组中索引 i 处的字符频率大于 0，则表示该字符存在于输入字符串中，并使用 std::cout 打印到标准输出流。
• 在 main 函数中，声明了一个字符串变量 input 并使用值“hello”进行初始化。这是将要计数和打印其不同字符的输入字符串。

程序输出

方法 2：使用集合跟踪不同字符

另一种方法是使用集合数据结构来跟踪不同字符。

步骤：

• 创建一个空集合来存储唯一字符。
• 遍历字符串并将每个字符插入集合中。
• 打印集合的元素，这将自动消除重复项。

实施

说明

• 在 printDistinctChars 函数中，声明了一个名为 charSet 的 std::set。集合是一种以排序顺序存储唯一元素的容器。在这种情况下，它用于存储输入字符串 str 中遇到的唯一字符。
• 然后，该函数使用基于范围的 for 循环遍历输入字符串中的每个字符 ch。
• 对于遇到的每个字符，它使用 insert 函数将字符插入到 charSet 集合中。由于集合只允许唯一元素，任何重复字符都不会被添加。
• 将所有字符插入集合后，该函数再次使用基于范围的 for 循环遍历 charSet 集合。
• 此循环使用 std::cout 将集合中的每个字符打印到标准输出流。由于集合会自动对其元素进行排序，因此字符将以排序顺序打印。
• 在 main 函数中，声明了一个字符串变量 input 并使用值“hello”进行初始化，这是将要打印其不同字符的输入字符串。

程序输出

复杂度

方法 1：使用数组计数出现次数

• 遍历字符串以计数出现次数： O(n)，其中 n 是字符串的长度。
• 打印不同字符： O(1) 到 O(256)，取决于不同字符的数量。
• 总体时间复杂度： O(n + k)，其中 k 是字符串中不同字符的数量。

方法 2：使用集合跟踪不同字符

• 将字符插入集合： O(n log n)，其中 n 是字符串的长度。这是因为对集合的每个插入操作通常具有对数时间复杂度。
• 打印不同字符： O(k)，其中 k 是字符串中不同字符的数量。
• 总体时间复杂度： O(n log n)，由集合插入操作主导。

在时间复杂度方面，当不同字符数量相对较少时（例如，对于具有有限字符集（如 ASCII）的字符串），方法 1 更有效，因为它避免了集合操作的开销。然而，方法 2 提供了简单性和自动去重，使其适用于代码可读性和实现简易性优先于性能的场景。

结论

总之，这两种方法都提供了在 C++ 中从字符串中提取不同字符的有效解决方案。方法 1 利用数组计数出现次数，提供了线性的时间复杂度 O(n) 用于计数，O(k) 用于打印，其中 k 是不同字符的数量。

另一方面，方法 2 采用集合来跟踪不同字符，由于对集合的插入操作，其时间复杂度为 O(n log n)，另外还有 O(k) 用于打印。

虽然方法 1 在字符集较小时效率更高，但方法 2 优先考虑简单性和自动去重，使其成为代码可读性和实现简易性至关重要的场景的理想选择。总的来说，两种方法之间的选择取决于问题的具体要求以及性能和简易性之间的权衡。