时间戳

首页 > 解决方案 > 打印列表中第一个、第二个出现的字符

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

问题描述

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

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) 中做到这一点？

标签： pythonalgorithm

解决方案

更改s = []为s = set()（显然对应append于add）。inover set 是 O(1)，不像inover list 是顺序的。

或者，使用正则表达式（O(n^2)，但相当快速和容易）：

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

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

推荐阅读