Arrays vergleichen

[Esto]

Hallo,

Gegeben sind zwei Arrays A, B. Beide Arrays haben die selben Elemente, nur die Reihenfolge kann unterschiedlich sein.
Sei N die Länge des Arrays. B hat genau ein Element weniger als A.
Ziel ist es nun einen Algorithmus zu finden, der in linearer Laufzeit (also O(n) ) die fehlende Zahl findet.
Es scheint leider nicht ganz meine Stärke zu sein, denn ich überlege mir immer wie ich vor gehen würde wenn mir die Mittel der Maschine zur Verfügung stehen.
Daher habe ich also eine relative naive Methode.
Ich nehme mir der Reihe nach ein Element aus A und vergleiche es mit jedem Element aus B. Wenn zwei Elemente gefunden die gleich sind, dann gehe zum nächsten Element und beginne von vorne.
Wenn ein Element aus A mit allen Elementen aus B verglichen wurde und es keine Übereinstimmung gab, dann breche ab => Element gefunden.
Nur leider benötige ich mit dieser Überlegung eine geschachtelte (for-)Schleife um zunächst eine Element aus A herauszugreifen (1.Schleife) um es dann mit allen Elementen aus B (2.Schleife zu vergleichen).
Das würde aber eine Laufzeit von O(n^2) bedeuten.

Ich hatte mir überlegt ein weiteres Array vom Typ Boolean zu implementieren, das zunächst überall mit false belegt ist.
Wenn zwei Zahlen gefunden wurden, die gleich sind, und es liegt an der Stelle i in B, dann wird im Boolean Array an der Stelle i der Wert auf true gesetzt, sodass beim nächsten Durchgang die Stelle i nicht mehr betrachtet wird. Aber das bringt mich leider nicht viel weiter.

Kann mir jemand sagen wie ich es besser machen kann?
MfG

 

[Landei]

Ganz praktisch würde ich die Elemente des kürzeren Array in ein [c]HashSet[/c] packen und dann für jedes Element des längeren Arrays testen, ob es im [c]HashSet[/c] vorhanden ist, bis das fehlende ermittelt ist. In der Praxis sollte dieses Vorgehen nahe O(n) sein.

Eine andere Variante ist, beide Arrays mit [c]java.util.Arrays.sort[/c] zu sortieren, und dann parallel durchzugehen, bis ein Unterschied auftaucht. Das ist dann allerdings O(n log n), aber immer noch besser als O(n^2).

Dritte Variante: Ich nehme das erste Element e des längeren Arrays. Dann teile ich das längere Arrays in zwei Teilarrays mit Elementen kleiner e und größer/gleich e. Das selbe mache ich mit dem kürzeren Array, wobei ich einmal das Element e entferne (falls es dieses Element nicht gibt, ist e selbst die gesuchte Zahl). Dann schaue ich nach, wo ich weitersuchen muss: Sind die "kleiner"-Arrays ungleich lang, muss dort das gesuchte Element sein, sind die "größer/gleich" -Arrays ungleich lang, muss es dort sein. Im Mittel hat dieses Verfahren auch O(n log n), im schlechtesten Fall O(n^2).

 

[codechaos]

Wenn du nicht prüfen sollst, ob die Arrays sich wirklich nur an einer Stelle unterscheiden, dann könntest du auch einfach die Summe der beinhaltenden Zahlen bilden und die Differenz zurück geben.