剑指offer 面试题50. 第一个只出现一次的字符（易）

将字符串与哈希表运用到极致的一道题

Question

在字符串 \(s\) 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 \(s\) 只包含小写字母。

示例: 

1
2
3
4
s = "abaccdeff"
返回 "b"
s = "" 
返回 " "
限制：0 <= s 的长度 <= 50000

测试用例

功能测试（字符串中存在只出现一次的字符；字符串中不存在只出现一次的字符；字符串中所有字符都只出现一次）。 特殊输入测试（字符串为 nulptr 指针）。

本题考点

考查应聘者对数组和字符串的编程能力。 考查应聘者对哈希表的理解及运用。 考查应聘者对时间效率及空间效率的分析能力。当面试官提示最直观的算法不是最优解的时候，应聘者需要立即分析出这种算法的时间效率。在想出基于哈希表的算法之后，应聘者也应该分析出该方法的时间效率和空间效率分别是 \(O(n)\) 和 \(O(1)\)。

Intuition

两个List一次扫描

res 保存当前遍历过程中只出现一次的字符，repeated 保存之前出现过的字符。由于 list.index 的时间复杂度为 \(O(1)\)，所以该方法的时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(n)\)。

一个Dict两次扫描

1、 遍历字符串 s ，使用哈希表统计 “各字符数量是否 \(\geq 1\) ，如果 \(\geq 1\)，就设置为 False。 2、再遍历字符串 s ，在哈希表中找到首个 “为 False ”，并返回。 Dict是有序的，所以可以这么用。该方法的时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(n)\)。

一个List两次扫描（最佳）

ASCII码，一共有256个字符，可以声明一个长度为 256 的List。进行两次扫描，第一次扫描，更新List上字符对应的值，时间复杂度为 \(O(n)\)。第二次扫描，读出第一个只出现一次的字符，时间复杂度为 \(O(n)\)。由于List长度固定为 256，int32的一个256的List，占用内存为 1KB，所以可以认为空间复杂度为 \(O(1)\)。

Code

  • 两个List一次扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstUniqChar(self, s: str) -> str:
        if not s:  return " "
        res = []
        repeated = []
        for char in s:
            if char in res:
                index = res.index(char)
                del res[index]
                repeated.append(char)
            elif char in repeated:
                pass
            else:
                res.append(char)
        return res[0] if len(res) else " "  # 注意啊，这里要加一个特判
  • 一个Dict两次扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def firstUniqChar(self, s: str) -> str:
        if not s:  return " "
        res = {}
        for char in s:
            if char in res:
                if  res[char]:
                    res[char] = False
            else:
                res[char] = True

        for char in res:
            if res[char]:
                return char
            
        return " "
  • 一个List两次扫描
1
2
3
4
5
6
7
8
9
10
class Solution:
    def firstUniqChar(self, s: str) -> str:
        if not s:  return " "
        res = [0] * 256
        for char in s:
            res[ord(char)] += 1
        for char in s:
            if res[ord(char)] == 1:
                return char
        return " "

Extension

原题拓展

在前面的例子中，我们之所以可以把哈希表的大小设为256，是因为字符（char）是8bit的类型，总共只有256个字符。但实际上字符不只是256个，比如中文就有几千个汉字。如果题目要求考虑汉字，那么前面的算法是不是有问题？如果有，则可以怎么解决？

有问题，可以直接使用 hash_map 来替代 List 解决问题。

相关问题

  • 定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如，从第一个字符串"We are students."中删除在第二个字符串“aeiou”中出现过的字符得到的结果是“WrStdnts."。为了解决这个问题，我们可以创建一个用数组实现的简单哈希表来存储第二个字符串。这样我们从头到尾扫描第一个字符串的每个字符时，用 \(O(1)\) 时间就能判断出该字符是不是在第二个字符串中。如果第一个字符串的长度是n，那么总的时间复杂度是 \(O(n)\)。
  • 定义一个函数，删除字符串中所有重复出现的字符。例如，输入"google”，删除重复的字符之后的结果是“gole”。这道题目和上面的问题比较类似，我们可以创建一个用布尔型数组实现的简单的哈希表。数组中的元素的意义是其下标看作ASCII码后对应的字母在字符串中是否已经出现。我们先把数组中所有的元素都设为false。以“google"为例，当扫描到第一个g时，g的ASCII码是103，那么我们把数组中下标为103的元素设为true。当扫描到第二个g时，我们发现数组中下标为103的元素的值是true，就知道g在前面已经出现过。也就是说，我们用 \(O(1)\) 时间就能判断出每个字符是否在前面已经出现过。如果字符串的长度是n，那么总的时间复杂度是 \(O(n)\)。
  • 在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词（Anagram）。例如，silent与listen、evil与live等互为变位词。请完成一个函数，判断输入的两个字符串是不是互为变位词。我们可以创建一个用数组实现的简单哈希表，用来统计字符串中每个字符出现的次数。当扫描到第一个字符串中的每个字符时，为哈希表对应的项的值增加1。接下来扫描第二个字符串，当扫描到每个字符时，为哈希表对应的项的值减去1。如果扫描完第二个字符串后，哈希表中所有的值都是0，那么这两个字符串就互为变位词。

举一反三

如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串中出现的次数，那么我们可以考虑基于数组创建一个简单的哈希表，这样可以用很小的空间消耗换来时间效率的提升。

Related Question

Question

请实现一个函数，用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是’g；当从该字符流中读出前6个字符"google”时，第一个只出现一次的字符是‘l’。

Intuition

字符只能一个接着一个从字符流中读出来。可以定义一个数据容器来保存字符在字符流中的位置。当一个字符第一次从字符流中读出来时，把它在字符流中的位置保存到数据容器里。当这个字符再次从字符流中读出来时，那么它就不是只出现一次的字符，也就可以被忽略了。这时把它在数据容器里保存的值更新成一个特殊的值（如负数值）。为了尽可能高效地解决这个问题，需要在 \(O(1)\) 时间内往数据容器里插入一个字符，以及更新一个字符对应的值。受面试题50的启发，这个数据容器可以用哈希表来实现。用字符的ASCII码作为哈希表的键值，而把字符对应的位置作为哈希表的值。实现这种思路的参考代码如下：

测试用例

功能测试（读入一个字符；读入多个字符；读入的所有字符都是唯一的；读入的所有字符都是重复出现的）。 特殊输入测试（读入0个字符）。

本题考点

考查应聘者对数组和字符串的编程能力。 考查应聘者对哈希表的理解及运用。 考查应聘者对时间效率及空间效率的分析能力。当面试官提示最直观的算法不是最优解的时候，应聘者需要立即分析出这种算法的时间效率。在想出基于哈希表的算法之后，应聘者也应该分析出该方法的时间效率和空间效率分别是 \(O(n)\) 和 \(O(1)\)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def firstAppearInStream(self, s: str) -> str:
        if not s:  return " "
        res = [-1] * 256
        input_char = input()
        count = 1  # count记录char出现的位置

        # 开始接收输入，以输入回车为结束，将输入保存在res中。
        while input_char != '\n':
            if res[ord(input_char)] > 0:  # res[ord(input_char)] > 0说明这是该字符第2次出现。
                res[ord(input_char)] = -2  # 设置值为-2代表chr(i)出现过多次
            elif res[ord(input_char)] == -1:  # 等于-1，也就是说这是该字符第一次出现，用res保存其出现顺序。
                res[ord(input_char)] = count  # res[i]的值保存chr(i)这个值在字节流中的顺序
            else:
                pass  # 最后一种情况是res[ord(input_char)] = -2说明这是该字符第n次第n次出现，不用做任何处理，保持其-2的值不变。
            input_char = input()
            count += 1

        # 开始在res中找只出现过一次，且输入位置比较靠前的字符
        order = count
        _char = " "
        for i in range(256):
            # res[i] > 0代表chr(i)只出现过一次
            # res[i] < order代表chr(i)出现位置靠前
            if res[i] > 0 and res[i] < order:
                order = res[i]
                _char = chr(i)

        return _char

在上述代码中，哈希表用数组 res 实现。数组中的下标为 i 的元素 res[i] 记录ASCIl码的值为 i 的字符出现的位置和次数。最开始的时候，数组中的所有元素都初始化为-1。当一个ASCII码为i的字符第一次从字符流中读出时，res[i]的值更新为它在字符流中的位置（从1开始 count = 1）。当这个字符再次从字符流中读出时（res[i]>0），res[i]的值更新为-2，意味着这个字符多次出现过。 当我们需要找出到目前为止从字符流里读出的所有字符中第一个不重复的字符时，只需要扫描整个数组，并从中找出最小的大于等于1的值对应的字符即可。这就是方法 firstAppearInStream 的功能。