Warum ist meine zweite Methode langsamer als meine erste Methode?

Question

Ich war leetcode Problem No. 387. First Unique Character in a String. Bei einer gegebenen Zeichenfolge wird das erste sich nicht wiederholende Zeichen gefunden und der Index zurückgegeben. Wenn es nicht existiert, gebe -1 zurück.

Beispiele:

s = "leetcode" 
return 0. 

s = "loveleetcode", 
return 2. 

Ich schrieb 2-Algorithmus:

Methode 1

def firstUniqChar(s): 
    d = {} 
    L = len(s) 
    for i in range(L): 
     if s[i] not in d: 
      d[s[i]] = [i] 
     else: 
      d[s[i]].append(i) 
    M = L 
    for k in d: 
     if len(d[k])==1: 
      if d[k][0]<M: 
       M = d[k][0] 
    if M<L: 
     return M 
    else: 
     return -1 

Dies ist sehr intuitiv, dh zuerst durch Schleifen über alle Zeichen einer Zählung Wörterbuch erstellen in s (dies kann auch mit einer Zeile in collections.Counter getan werden), dann eine zweite Schleife nur die Schlüssel überprüfen, deren Wert eine Liste der Länge 1 ist. Ich denke wie Ich habe 2 Schleifen gemacht, es muss einige redundante Berechnungen haben. Also habe ich den zweiten Algorithmus geschrieben, der meiner Meinung nach besser ist als der erste, aber in der Leetcode-Plattform läuft der zweite viel langsamer als der erste und ich konnte nicht herausfinden warum.

Methode 2

def firstUniqChar(s): 
    d = {} 
    L = len(s) 
    A = [] 
    for i in range(L): 
     if s[i] not in d: 
      d[s[i]] = i 
      A.append(i) 
     else: 
      try: 
       A.remove(d[s[i]]) 
      except: 
       pass 

    if len(A)==0: 
     return -1 
    else: 
     return A[0] 

Die 2. eine nur Schleife einmal für alle Zeichen in s

Answer 1

Ihre erste Lösung ist O(n), aber Ihre zweite Lösung ist O(n^2), als Methode A.remove wird Schleifen über Elemente von A .

Answer 2

Wie andere gesagt haben - mit list.remove ist ziemlich teuer ... Ihre Verwendung von collections.Counter ist eine gute Idee.

Sie müssen die Zeichenfolge einmal einscannen, um Uniques zu finden. Dann wahrscheinlich das, was besser ist, ist der Reihe nach wieder zu scannen und den Index des ersten eindeutigen nehmen -, die Ihre potentiellen Code macht:

from collections import Counter 

s = "loveleetcode" 

# Build a set of unique values 
unique = {ch for ch, freq in Counter(s).items() if freq == 1} 
# re-iterate over the string until we first find a unique value or 
# not - default to -1 if none found 
first_index = next((ix for ix, ch in enumerate(s) if ch in unique), -1) 
# 2