Normal
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).
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).
