Warum muss ich summieren, um die Wiederholungszahl zu finden?

Question

Problem: Sie erhalten eine Folge von Zahlen von 1 bis n-1, wobei sich eine der Zahlen nur einmal wiederholt. (Beispiel: 1 2 3 3 4 5). Wie findest du die Wiederholungszahl?

Sehr oft ist die so genannte "intelligente" Antwort auf diese Frage, um es zusammenzufassen und den Unterschied von der erwarteten Summe zu finden. Aber warum nicht einfach die Liste durchgehen und die Nummer davor überprüfen? Beide sind O (n). Fehle ich etwas?

Answer 1

Die "intelligente" Antwort ist die beste Lösung, wenn die Liste nicht sortiert ist, weil sie jedes Element nur einmal besucht und O (1) zusätzlichen Speicherplatz verwendet. Wenn die Liste sortiert ist, gibt es sogar eine O (log n) -Lösung: Sie können eine binäre Suche durchführen. Wenn Sie sich das zentrale Element ansehen, können Sie sehen, ob die doppelte Zahl vor oder nach diesem Element liegt, und fortfahren, bis Sie es gefunden haben.

Beispiel:

1 2 2 3 4 5 6 

Das zentrale Element 3 ist, aber es ist in der vierten Position, so dass die doppelte muss, bevor es sein. Nächste Prüfung ist die 2 in der zweiten Position, so haben wir nach der zweiten Position suchen usw.

Answer 2

Wenn die Zahlen sortiert sind, dann fehlt nichts.

Answer 3

Um zu wissen, die misterious Nummer x Sie müssen nur alle Zahlen in der Folge summieren:

S = sum(sequence) 
S = sum(from 1 to (n - 1)) + x 

sum(from A to B) = 1/2 * (A + B) * (B - A + 1) 

sum(from 1 to (n - 1)) = 1/2 * (1 + (n - 1)) * ((n - 1) - 1 + 1) = 1/2 * n * (n - 1) 

x = S - sum(from 1 to (n - 1)) 

x = S - 1/2 * n * (n - 1)