Algorithmus erhalten Sie eine neue Liste, die kein doppeltes Element enthält, indem Sie 2 Elemente in einem großen Array hinzufügen

Question

Ich kann nur an diesen naiven Algorithmus denken. Irgendein besserer Weg? C/C++, Ruby, Haskell ist in Ordnung.

arry = [1,5,.....4569895] //1000000 elements ,sorted , no duplicated 
newArray = Hash.new 
for (i = 0 ; i < arry.length ;i++) 
{ 
     for (j = 0 ; j < arry.length ;j ++) 
     { 
       elem = arry[i] + arry[j] 
       if (! newArray.key?(elem)) 
       { 
        newArray [elem] = arry[i] + arry[j] 
       } 

     } 

} 

EDIT: Entschuldigung. Ich habe diskreten Wert im Array, anstelle von [1..1000000]

Answer 1

Es wäre effizienter, den Algorithmus in zwei verschiedene Schritte zu trennen. (Warnung: Pseudocode voraus)

Zuerst erstellen Sie n-1 Listen, indem Sie die restlichen Elemente zum i-ten Element hinzufügen. Dies kann für jede Liste parallel erfolgen. Beachten Sie, dass die resultierenden Listen sortiert werden.

Zweite Verwendung merge sort, um die Ergebnislisten zusammenzuführen. Sie können dies parallel tun, z.B. fuge newArray [0] - newArray [i], newArray [2] - newArray [1-i], ... und dann wieder, bis du nur eine Liste hast.

Answer 2

Wenn die Bedingung besagt, dass Sie alle Artikel im Bereich hinzufügen können, dann ist die einzige Möglichkeit, die ich mir vorstellen kann, zu überprüfen wenn die Summe noch nicht in der Ergebnisliste ist. Für jede Zahl x gibt es x verschiedene Zusätze, die zu x führen. (Oder x/2, wenn Sie denken, dass 1 + 2 und 2 + 1 die gleiche Addition ist).

Answer 3

Es gibt eine offensichtliche Optimierung: Machen Sie die zweite Schleife an der Indice I beginnen, auf diese Weise werden Sie vermeiden, dass x + y und y + x.

Wenn Sie einen Satz nicht verwenden möchten, können Sie die Tatsache verwenden, dass die Artikel sortiert sind. So können Sie N Listen erstellen und sie zusammenführen, während Sie die Duplikate entfernen.

Answer 4

Ich fürchte, die beste Worst-Case-Zeit Komplexität ist O (n). Für die Eingabe {2 , 2 , 2 , ...}, erhalten Sie kein Duplikat, wenn Sie diese Zahlen hinzufügen. Angenommen Hasheinfügungen sind O (1), haben Sie bereits den besten Algorithmus ...