python - 打印列表中第一个、第二个出现的字符

Question

我正在研究一个简单的算法，打印出现两次或更多次的第一个字符。

for eg:

string ='abcabc'
output = a

string = 'abccba'
output = c

string = 'abba'
output = b

我所做的是:

string = 'abcabc'
s = []

for x in string:
     if x in s:
          print(x)
          break
     else:
          s.append(x)


output: a

但是它的时间复杂度是O(n^2)，我如何在O(n)中做到这一点？

Answer 1

将 s = [] 更改为 s = set() (显然相应的 append 为 add ). in over set 是 O(1)，不像 in over list 是顺序的。

或者，使用正则表达式 (O(n^2)，但又快又简单):

import re
match = re.search(r'(.).*\1', string)
if match:
    print(match.group(1))

正则表达式 (.).*\1 表示“我们稍后会记住的任何字符，任意数量的中间字符，然后再次记住的字符”。由于正则表达式是从左到右扫描的，因此它将根据需要在 "abba" 中找到 a 而不是 b。