m ganze Zahlen fehlen in einem Array der Größe n

Dies ist eine interessante Frage, die mir vor einiger Zeit schon begegnet ist und einige Probleme hatte, sie zu lösen.m ganze Zahlen fehlen in einem Array der Größe n

Es gibt einen unsortierte Integer-Array der Größe N mit Zahlen gespeichert 1,2 .., N + M , mit M ganzen Zahlen von ihm fehlen. M und N sind vor hand bekannt. Schreibe einen Algorithmus, um die fehlenden M Ganzzahlen auf effizienteste Weise zu finden.

Mapping es auf ein Array der Größe N + M versucht hat, so daß die i th Index enthält, das Element mit dem Wert i, aber dies erfordert 2 scans (1 für die Abbildung, 1 zum Auffinden der M fehlenden Nummern).

Das Buch, in dem ich darauf stieß, erwähnt eine einzige Scan-Lösung ist möglich, aber ich konnte es nicht erreichen. Irgendwelche Ideen, wie man das macht?

Quelle

2012-11-09 sanz

Könnten Sie bitte den einen Scan Algo aufschreiben? Vielen Dank. –

Diese Frage scheint sehr lokal zu sein, und Sie haben auch keinen Hinweis darauf gegeben, dass Sie versucht haben, das Problem selbst zu lösen. – lockstock

@lockstock tut mir leid. Ich habe die Frage bearbeitet. Hoffe das hilft. – sanz

Sie können dies mit einer doppelt verknüpften Liste tun, die auf einem Array angeordnet ist. diese Position zu entfernen (überspringen) aus der verketteten Liste

position 1 2 3 4 5 6 ... 
next  2 3 4 5 6 7 ... 
prev  0 1 2 3 4 5 ...

Auf dem Durchgang durch den Eingang Sie Index in die Position zu jeder Eingangsnummer und Aktualisieren der verknüpften Liste entspricht. Am Ende der Eingabe enthält die verknüpfte Liste nur die nicht besuchten Positionen.

Quelle

2012-11-09 03:40:11

Aber müssen Sie die verknüpfte Liste nicht durchlaufen, um die fehlenden ganzen Zahlen auszudrucken? Es ist '> 1' Schleife, wie ich es verstehe? – irrelephant

@irrelephant Sie wetten, vorausgesetzt, Sie möchten sie drucken. Ich denke nicht, dass du es vom Standpunkt der Zeitkomplexität besser machen kannst, dass "O (N) + O (M)" weil du bis zum Erreichen des Endes von "N" nicht das letzte der fehlenden aus dem M wissen kannst '. Wenn Sie bereits mit dem Drucken begonnen haben, könnte das letzte "N" Ihre Ausgabe verderben, indem es etwas enthält, das Sie bereits gedruckt haben. Ich bin sicher, dass Sie wahrscheinlich besser aus einer Raumkomplexität Perspektive tun können, wenn M << N, wie die [ziemlich beeindruckend aussehende mathematische Antwort] (http://stackoverflow.com/a/3492967/1756702) in den obigen Kommentaren verlinkt scheint zu tun. –

Ich hätte dort nicht Big-O Notation verwenden sollen. Ich wollte sagen, ich glaube nicht, dass du es nicht besser machen kannst als einen einzigen Durchgang durch "N" und "M", wenn du "M" drucken willst. –

m ganze Zahlen fehlen in einem Array der Größe n

Antwort

Verwandte Themen