使用布尔数组在O(n)中查找字符串的第一个非重复字符？

Question

我的问题与之前的问题有关

在字符串中查找第一个未重复的字符.

在我的一次采访中,我被要求编写一个函数来确定时间O(n)中字符串中的第一个唯一字符,使用长度为n的布尔数组作为额外空间.也就是说,仅使用O(n)复杂度和长度为n的bool数组找到字符串中的第一个非重复字母.有人可以建议如何使用bool数组解决它？

Answer 1

好吧,如果字符集的大小是不变的...例如,比如0-255 ......

扫描字符串寻找字符0.

然后扫描字符串寻找字符1.

然后扫描字符串寻找字符2.

...

最后,扫描字符串以查找字符255.

这需要256*n次操作,即O(n).

在每次扫描期间,如果字符是唯一的,请在位图中标记其位置.最后在第一个标记位置返回字符.(或者只使用k + log(n)位记录第一个唯一字符及其位置.使用硬编码查找表或任何非常小的n;否则,n位是慷慨的.)

虽然不知怎的,我怀疑这不是面试官的想法.

Answer 2

有两个布尔数组，seenOnce 和 sawMany。循环遍历字符串填充数组。再次循环字符串，检查该字符是否在 sawFirst 中但不在 sawMany 中。如果这是您的第一个非重复角色。

这是 python 中的一些示例代码。

subject = "ttojxxlma"

seenOnce = [False for i in range(256)]
seenMany = [False for i in range(256)]

for c in subject:
    index = ord(c)
    if seenOnce[index] == False:
        seenOnce[index] = True
    else:
        seenMany[index] = True

for c in subject:
    index = ord(c)
    if seenOnce[index]==True and seenMany[index] != True:
        print(c)
        break

好吧，仍然使用布尔数组（或Python列表=P）。要仅使用一个数组，您可以使用一个字符数双倍的数组。不是访问第二个数组，而是将索引加倍并访问大的数组。但那只是混乱。

不确定是否可以用更少的空间来完成。