Ich arbeite durch Analyse der Algorithmen-Klasse zum ersten Mal und fragte mich, ob jemand mit dem folgenden Beispiel helfen könnte. Ich glaube, ich habe es für eine O (n) -Komplexität gelöst, aber ich frage mich, ob es eine bessere Version gibt, an die ich nicht O (logn) denke?Analyse von Algorithmen - Finden Sie fehlende Ganzzahl in Sorted Array besser als O (n)
Let A = A [1] = ... < < = A [n + 1] ein sortiertes Array von n verschiedenen ganzen Zahlen sein, wobei jede ganze Zahl in dem Bereich [1 ... n + 1]. Das heißt, in A fehlt genau eine ganze Zahl von {1, ..., n + 1}. Beschreiben Sie einen Efficeint-Algorithmus, um die fehlende ganze Zahl zu finden. Analysieren Sie die Worst-Case-Komplexität (Anzahl der Zugriffe auf Array A) Ihres Algorithmus.
Die Lösung, die ich habe, ist relativ einfach, und ich glaube, dass im schlimmsten Fall N Komplexität führt. Vielleicht denke ich über das Beispiel nach, aber gibt es eine bessere Lösung?
Meine Lösung
for(i = 1; i < n +1; i++) :
if(A[i-1] > i) :
return i
Die Logik dahinter ist, da er sortiert wird, muss das erste Element 1 sein, muss die zweiten 2 sein, und so weiter und so fort, bis das Element in dem Array ist Größer als das Element, das es sein sollte, wurde ein Element verpasst, das Element zurückgegeben, das es sein sollte, und wir haben das fehlende Element.
Ist dies die richtige Logik? Gibt es einen besseren Weg?
Vielen Dank für das Lesen und danke im Voraus für die Unterstützung.
Ja. Es gibt eine bessere Lösung. Tipp: Müssen Sie wirklich jedes Element im Array betrachten? – aquinas
Würden Sie bitte Ihre Aussage des Problems aufräumen? (1) Wenn die A's verschieden sind, bedeutet das, dass sie nicht gleich sind; Warum also nicht einfach "A [1] Scott