Finden Sie alle Paare (x, y) in einem unsortierten Array, so dass x + y = z

Question

Ich habe n Zahlen und eine Zahl z. Ich möchte einen Algorithmus (Pseudocode) erstellen, um herauszufinden, ob es Paare (x, y) gibt, die x + y = z in O (nlogn).

Ich dachte, dass ich den Quicksort-Algorithmus ausführen kann. Dann habe ich 2 Arrays: Array1 (mit Elementen < Pivot) und Array2 (mit Elementen> Pivot). Wenn das erste Element im Array < z ist, dann kann ich alle anderen Elemente in Array1 überprüfen, um Paare zu finden, die x + y = z. sonst, wenn das erste Element in Array1 ist> z dann gehe ich zu Array2 und mache die gleiche Prozedur. Ist mein Vorschlag wahr?

Answer 1

Sortieren Sie zuerst das Array.
Setzen Sie dann einen Zeiger/Index auf jedes Ende des sortierten Arrays.
Wenn sie sich zu z zusammenfassen, behalten Sie es und verschieben Sie beide Zeiger in die Mitte.
Wenn die Summe kleiner als z ist, bewegen Sie den Zeiger am kleinen Ende in Richtung Mitte.
Wenn die Summe größer als z ist, bewegen Sie den Zeiger am großen Ende in Richtung Mitte.
Wenn die Zeiger sich treffen, sind Sie fertig.

Answer 2

Sie müssen keine bereits sortierte Sequenz sortieren, sondern nur suchen.

Pseudo-Code:

sort(sequence) // O(NlogN) sorts are well known 
for element in sequence: // O(N) loop 
    target = z - element // constant (assuming fixed size arithmetic) 
    if target > min_element and target < max_element: // constant 
     found = binary_search(target, sequence) // O(LogN) search 

Komplexität: O (NlogN (sortiert) + (N (loop) * LogN (Suche))) = O (NlogN), je nach Bedarf

Answer 3

Die Idee mit der Pivot wird nicht funktionieren, weil es keinen guten Kandidaten für einen Pivot gibt, und weil das Prüfen unsortierter Halbbereiche eine O (n) Task bleiben würde, die n/2 mal ausgeführt werden muss, für die Gesamtkomplexität von O (n).

Sie können es in O (n) ohne Sortierung tun, indem Sie alle Elemente zu einer Hash-Tabelle hinzufügen und dann für jedes Element x überprüfen, dass z-x Element auch vorhanden ist. Eine Situation mit x=z/2 ist ein Sonderfall, weil Sie sicherstellen müssen, dass zwei z/2 Werte im Eingabe-Array vorhanden sind.