Optimierung einen Python-Skript

Question

Ich habe versucht, die folgenden Aufgaben in Python zu vervollständigen:

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

ich es ein einfaches Skript erstellt, wie kann unten gesehen werden, aber es gibt einen Laufzeitfehler für die 7. Test Ich glaube, das liegt daran, dass der Code vielleicht zu lange dauert, daher benötige ich Unterstützung, um ihn zu optimieren. Ich habe Karten- und Filterbefehle betrachtet und versucht, sie zu implementieren, ohne Erfolg.

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)) 

Answer 1

können Sie versuchen, valid_usernames zu einem set anstelle eines list ändern.

Eine Liste list_a Betrieb x in list_a (im Durchschnitt) nimmt lineare Zeit.

Für einen Satz set_a Betrieb x in set_a dauert (im Durchschnitt) konstante Zeit.

(Quelle: https://wiki.python.org/moin/TimeComplexity)

Diese einfache Änderung der Laufzeit ein wenig verbessern könnte.

Was mich auch als potenziell sehr langsam auffällt, ist dieses Fragment:

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

Wenn Sie jedoch diese verbessern wollen, müssen Sie eine ganz andere Datenstruktur denken, über die Verwendung.

Answer 2

Warum versuchen Sie nicht

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

Answer 3

Warum Sie nicht über eine Lookup dict mit einem Zähler und lösen diese in O (N) Zeit verwenden?

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