Algorithmus zu überprüfen, ob Zahlen in 2 Arrays zu einer geben Nummer

Question

Ich würde gerne wissen, was ist der zeitaufwendigste Algorithmus dafür.

Bei 2-Arrays, a und b, überprüfen Sie, ob alle 2 Mitglieder - ein von a und ein von b bis zu einer bestimmten Anzahl h hinzuzufügen.

Was ist Ihrer Meinung nach der schnellste Algorithmus für dieses Problem? Ich wiederhole einfach beide Arrays und versuche die Lösung zu finden, die sehr teuer ist. Es ist O(mn), denke ich, wo m und n sind die Längen der Arrays a bzw. b. Es ist auch nicht notwendig, dass beide Arrays die gleiche Länge haben. Kennst du einen Algorithmus, der schneller ist? Beachten Sie für die Größe, dass die maximale Länge beider Arrays ungefähr 100000 beträgt.

Vielen Dank.

P.S. Diese Frage ist kein Duplikat, da es darum geht, die Ganzzahlen in zwei verschiedenen Arrays zu finden, nicht in einem.

Answer 1

könnten Sie ungerade verwenden/sogar auf etwa Ihre Zeit halbieren:

Split a und b in 2 Reihen je, was zu aeven, AODD, beven, Bodd. Wenn n gerade ist, vergleiche (aeven + beven) und (aodd + bodd). Wenn n ungerade ist, vergleiche (aeven + bodd) und (aodd + beven).

Also, wenn | a | = 20, und | b | = 20 würden Sie 400 Tests haben. Wenn wir ungefähr die gleiche Anzahl von ungeraden und even in jedem Array annehmen, | aeven | (und andere Sub-Arrays) wird ca. 10, so dass Sie 10 * 10 + 10 * 10 Tests oder ca. 200 haben.

Plus natürlich, bestellen Sie die Arrays und den Test für jeden Wert im ersten Array zu stoppen, wenn die Summe ist größer als n.

Answer 2

Als heuristische Verbesserung können die Arrays vorher sortiert werden. Wenn die n nicht negativ ist, sortieren Sie die Arrays A und B in nicht aufsteigender Reihenfolge. Angenommen, die äußere Schleife iteriert das erste Array in dieser sortierten Reihenfolge und die innere Schleife iteriert das zweite Array in dieser sortierten Reihenfolge, wobei die Summanden a bzw. b berücksichtigt werden. Die Iteration der inneren Schleife kann beendet werden, sobald kleiner als n ist.

Ebenso, wenn n negativ ist, können die Arrays in nicht abnehmender Reihenfolge sortiert werden; die innere Schleife kann beendet werden, sobald a+b größer als n ist.

Dies reduziert jedoch nicht die Zeitkomplexität im ungünstigsten Fall, da im ungünstigsten Fall immer noch jedes Zahlenpaar im Eingang überprüft wird.

Answer 3

Sie können eines der beiden Arrays sortieren, z. B. das Array b, und dann das Array a durchlaufen. Verwenden Sie für jedes Element in a die binäre Suche, um ein Element in b zu finden, das "übereinstimmt", d. H. Addiert bis h. Dann ist die Komplexität O(n log n) für die Sortierung plus für die Iteration und binäre Suche.