Was ist der schnellste Weg, um alle fehlenden Nummern in unsortiertem Array zu finden

Question

Ich fand diese Antwort: Quickest way to find missing number in an array of numbers, das ist toll, wenn Sie nur eine Nummer fehlt haben.

Weiter zu dieser Frage - Ich habe mich gefragt, was ist die beste (und schnellste) Möglichkeit, alle fehlenden Zahlen zu finden und auch das unsortierte Array zu sortieren. (Für das Beispiel ist das Array wie das in der verknüpften Frage beschriebene - die Array-Größe ist 100, mit Zufallszahlen von 1-100, aber einige von ihnen fehlen)

Answer 1

Offensichtlich sind die Zahlen in einem bestimmten Bereich oder es macht keinen Sinn, über fehlende Zahlen zu sprechen. Daher kann eine counting sort angewendet werden. Führen Sie dann einen linearen Scan durch das Array durch, um die Löcher zu finden. Alternativ könnten Sie die Zählungen vom Sortierschritt scannen, um die fehlenden Elemente zu finden.

Dies alles läuft in O (n).

Beispiel: Das folgende Array ist mit 6,1,7,8,3,4,9,1,10,3 angegeben.

nun berechnen, wie oft jede Zahl in dem Feld erscheint einmal durch das Array, indem Sie und Erhöhen der Zählung für jede angetroffen Nummer:

number 1 2 3 4 5 6 7 8 9 10 
count 2 0 2 1 0 1 1 1 1 1 

Sie sofort sehen, dass 2 und 5 0 Mal erschienen und sind daher fehlt.

Die Zählungen können auch verwendet werden, um ein sortiertes Array zu erstellen: Wir brauchen 2 mal 1, 2 mal 3, 1 mal 4 usw.