schnellste art mengendifferenz zweier int-arrays zu berechnen - ideen?
-
Hallo,
ich habe 2 int - arrays die mir eine einfach Index-menge darstellen.
Ich will nun die differenz beider haben, also sowas:{2,3,6,9,1} , {2,6} = {3,9,1}
ich könne sie vorher noch sortieren lassen, evtl. wäre dann ein schneller weg gefunden?
oder komme ich um 2 for-schleifen nicht drum-rum?
Danke für ideen
-
Zuerst sortieren, dann parallel durchlaufen, das kommt zusammen auf O(n log n).
-
Vom ersten Array nen Suchbaum erstellen, dann versuchen das zweite einzufügen. Jedesmal, wenn es gelingt, hast du ein gesuchtes Element. Dürfte aber die gleich Laufzeit haben (die glaube ich auch nicht zu toppen ist
)
-
wenn die zahlen nicht zu groß sind, kannst du ein bool array erstellen das die größe der größten zahl + 1 hat (bei dir 9 + 1). dann läufst du das erste array durch und setzt alle felder im bool array auf true, wenn die zahl im array ist (barray[2] = true, barray[3] = true...). Dann das zweite array durchlaufen und die im zweiten array vorhandenen zahlen im bool array wieder auf false setzen (barray[2]=false,barray[6]=false). Dann durchläufst du das erste array nocheinmal und schaust, ob die entsprechenden zahlen im bool array noch true sind.
Bashar schrieb:
Zuerst sortieren, dann parallel durchlaufen, das kommt zusammen auf O(n log n).
Wie kommst du darauf, dass es zusammen O(n log n) ist? Das sortieren braucht ja schon O(n log n).
-
uber schrieb:
Wie kommst du darauf, dass es zusammen O(n log n) ist? Das sortieren braucht ja schon O(n log n).
Und das durchlaufen kostet O(n), macht zusammen immer noch O(n log n).
-
Ach, dass ist doch bescheißen. :p Dieses O(n) macht schon was aus, auch wenn man immer so tut als wäre es nix.
-
Macht es auch, aber nicht hier. Lies dir mal was zur O-Notation an.
-
uber schrieb:
Ach, dass ist doch bescheißen. :p Dieses O(n) macht schon was aus, auch wenn man immer so tut als wäre es nix.
Die O-Notation direkt sagt nichts über die reale Ausführungsgeschwindigkeit aus.
Außerdem könnte man hier mittels radix-sort sortieren und O(n) erreichen :p