优化Python脚本

我一直在试图完成在Python以下任务：优化Python脚本

http://codeforces.com/problemset/problem/4/C

我创建了一个简单的脚本，它可以看到下面，但它返回一个运行时错误的第七次测试。我相信这是由于代码耗时过长，所以我需要优化它的帮助。我已经看过地图和过滤器命令，并试图实现它们，但没有成功。

a=int(input()) 
entered_usernames=[] 
n=0 
while n<a: 
    y=input() 
    entered_usernames.append(y) 
    n+=1 

valid_usernames=[] 
for i in entered_usernames: 
    if i not in valid_usernames: 
     valid_usernames.append(i) 
     print('OK') 
    else: 
     count=1 
     while i+str(count) in valid_usernames: 
      count+=1 
     valid_usernames.append(i+str(count)) 
     print(i+str(count))

来源

2017-07-25 Sharky Kesa

什么是错误？发布整个错误 –

而我在valid_usernames比打印i +计数 – Vaibhav

这种类型的练习通常是为学生使用散列表，在Python中称为dictionnaries。请参阅@zwer响应。 – Wli

你可以尝试改变valid_usernames到set而不是list。

对于一个列表list_a操作x in list_a需要（平均）线性时间。

对于一套set_a操作x in set_a需要（平均）恒定时间。

（来源：https://wiki.python.org/moin/TimeComplexity）

这个简单的变化可以提高运行了一下。

什么也令我可能很慢是这样的片段：

while i+str(count) in valid_usernames: 
     count+=1

但是，如果你想改善这一点，你需要考虑使用一个完全不同的数据结构。

来源

2017-07-25 10:37:57 maestromusica

你为什么不尝试

valid_usernames.append(i+str(valid_usernames.count(i))) 
print(i+str(valid_usernames.count(i))

来源

2017-07-25 10:39:07

你为什么不使用查找dict用计数器和O（n）的时间解决这个问题？

total = int(input()) # get the first input (total usernames) 
database = {} # our 'database'/lookup dict 
candidates = [input() for _ in range(total)] # pick usernames from the input 
for candidate in candidates: # loop through each candidate 
    if candidate in database: # already used, print with a counter 
     print(candidate + str(database[candidate])) 
     database[candidate] += 1 # increase the counter 
    else: # the candidate doesn't exist in the 'database'... 
     print("OK") 
     database[candidate] = 1 # initialize counter for the next time

来源

2017-07-25 10:44:04 zwer

这可能是最好的解决方案，存储发生次数而不是名称本身 –

优化Python脚本

回答

相关问题