c - 查找字符串中的第一个非重复字符

Question

我在一次采访中被问到这个问题。我的回答：“创建一个大小为 26 的数组。按每个字符遍历字符串并计算数组中的字符数。通过在字符串中再次遍历并检查该字符是否不重复来检查第一个非重复字符。” 如果字符串包含大量字符，例如 10000 种字符而不是 26 种字母，该怎么办。

Answer 1

您可以使用更少的内存来实现您的原始算法。由于您不关心字符在 1 以上重复多少次，因此字母表中每个字符只需要 2 位。当增加一个已经大于 1 的值时，只需保留该值即可。算法的其余部分保持不变。

如果内存不是限制，则有一种更快的算法，不需要再次遍历字符串。允许字母表中的每个字母用ListNode. 然后有两个列表，list1和list2，一开始是空的。list1包含仅出现一次的list2字母，以及包含多次出现的字母。对于输入字符串中的每个字母，获取对应的ListNode，比如说node。如果node不在任一列表中，请将其放在list1. 如果node已经在 中list1，则将其取出并放入 中list2。输入字符串处理后，如果list1为空，则没有非重复字符。否则，与第一个节点对应的字符list1是第一个不重复的字符。

按照这个指向 IDEONE的链接来实现基于列表的算法。

Answer 2

你给出了蛮力的答案。一个聪明的解决方案是保留一个字母大小的数组，我们称之为x，每个项目最初为 -1。然后通过字符串一次；如果当前字符的x值为 -1，则将其更改为当前字符的索引，否则如果当前字符的x值大于 0，则将其更改为 -2。在字符串的末尾，检查x数组中的每个位置，跟踪最小的正值和相关的字符。我在我的博客中的 Scheme 中实现了该算法。

Answer 3

1. Start reading the string character-by-character
2. Put each character in HashMap
3. Return the first character which has conflict

Pros: You don't need to create a BitMap/Bit-Array in advance

Cons: The HashMap can grow to as much as number of characters in string, if it does not encounter repeating character (or if there is no repeating character)

Answer 4

• 您可以使用树状数据结构而不是数组。
• 如果我们的字符串不是太长，则逐个字符地遍历字符串并检查您是否设法再次找到它。缺点：最坏情况下的 n^2 运行时间
• 为第一遍构建每个字符的哈希，然后分别检查每个桶。应该与上述方法结合使用，我不确定它是否会显着减少运行时间 - 这取决于您的真实数据。