Ich stieß auf eine Frage, wenn ich this LeetCode problem lösen. Obwohl meine Lösung vom System akzeptiert wurde, habe ich immer noch keine Idee, nachdem ich online nach der folgenden Frage gesucht habe: What is the time complexity of dict.keys() operation? Gibt es eine Ansicht der Schlüssel oder eine echte Liste (speichert im Speicher) der Schlüssel zurück?Was ist die zeitliche Komplexität von dict.keys() in Python?
In Python 2 ist es O (n), und es erstellt eine neue Liste. In Python 3 ist es O (1), aber es gibt keine Liste zurück. Um ein zufälliges Element aus dem keys eines Dikters zu zeichnen, müssen Sie es in eine Liste konvertieren.
Es klingt, als ob Sie wahrscheinlich random.choice(d.keys()) für Teil 3 dieses Problems verwendet haben. Wenn ja, war das O (n), und du hast es falsch verstanden. Sie müssen entweder Ihre eigene Hash-Tabelle implementieren oder eine separate Liste von Elementen verwalten, ohne die durchschnittlichen O (1) -Einfügungen und Löschungen zu vernachlässigen.
Ich habe 'return self.elements.keys() [randint (0, len (self.elements) - 1)]' 'und es wurde akzeptiert (' self.elements ist ein dict-Objekt'). – Jason
@Jason: Ja, das ist nicht O (1). – user2357112
Wie du gesagt hast "In Python 3 ist es O (1)". Wenn 'self.elements.keys()' 'O (1) 'ist, würde der gesamte Ausdruck in' O (1) 'laufen. Wenn ich Fehler gemacht habe, korrigiere mich bitte :) – Jason
Die Komplexität ist '0 (1)' in Python 3.x. In Python 2.x gibt es eine Liste zurück, so dass es "0 (n)" braucht, um es zu füllen oder etwas nachzuschauen. – ozgur
Fragen Sie nach Python2 oder Python3? –
@ozgur - True, aber 'für _ in {} .keys(): pass 'ist' O (n) 'in beiden Versionen. –