Wie kann man einen

Bei einem sortierten Array von Ganzzahlen möchte ich die Anzahl der Paare ermitteln, die sich zu summieren . Wenn beispielsweise , beträgt die Anzahl der Paarsummen . $0$ $\{-3,-2,0,2,3,4\}$ $2$

Sei die Anzahl der Elemente im Eingabearray. Wenn ich die binäre Suche verwende, um die additive Inverse für ein Element im Array zu finden, lautet die Reihenfolge . Wenn ich alle Elemente in der Menge durchlaufe, ist die Reihenfolge . $N$ $O(\log N)$ $O(N\log N)$

Wie finde ich einen Algorithmus der Ordnung ? $O(N)$

algorithms Laura
quelle

Das

SUM-Problem bezieht sich normalerweise auf ein etwas anderes Problem, bei dem versucht wird, eine Menge von

Elementen aus dem Eingabearray

so zu finden, dass sie sich zu Null summieren. In einem bestimmten Berechnungsmodell ist es unmöglich, einen linearen Zeitalgorithmus für

oder für ein gerades

. Siehe diese Frage .

k

$k$

k

$k$

A

$A$

k = 2

$k=2$

k

$k$

Juho

Antworten:

Sei das sortierte Eingabearray. Behalten Sie zwei Zeiger und , die durch die Elemente in . Der Zeiger geht durch den "linken Teil" von , dh die negativen ganzen Zahlen. Der Zeiger macht dasselbe für den "rechten Teil", die positiven ganzen Zahlen. Im Folgenden werde ich eine Pseudocode-Lösung skizzieren und der Einfachheit halber annehmen . Ausgelassen sind auch die Prüfungen für die Fälle, in denen es in nur positive oder nur negative ganze Zahlen gibt . $A$ $l$ $r$ $A$ $l$ $A$ $r$ $0 \notin A$ $A$

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l]) 
     --left;
   else 
     ++right;

Es ist offensichtlich, dass der Algorithmus Zeit benötigt. $O(N)$

Juho
quelle

Sie sollten wahrscheinlich ein Argument für die Richtigkeit hinzufügen.

Raphael

-1

Nach meinem Verständnis scheint der einfachste Ansatz darin zu bestehen, eine Hash-Tabelle zu verwenden, H = {a [0] = wahr, .., a [n-1] = wahr}. Diese Hash-Tabelle kann in O (n) -Zeit erstellt werden. Sobald die Hash-Tabelle erstellt ist, durchlaufen Sie A [0, .., n-1] und prüfen Sie, ob H [-1 * a [i]] vorhanden ist. Wenn dies der Fall ist, erhöhen Sie einen Zähler um 1 und geben Sie das Endergebnis zurück. Dies ist eindeutig O (n).

Juspreet Sandhu
quelle

Die Ausdrücke H = {a [0] = wahr, .., a [n-1] = wahr} und A [0, .., n-1] ergeben für mich keinen Sinn. Bei Verwendung einer Hash-Funktion darf das Array nicht einmal sortiert werden. Algorithmen, die die Hash-Funktion verwenden, verwenden jedoch einige pseudozufällige Eigenschaften der Hash-Funktion. Im schlimmsten Fall werden alle Elemente demselben Hashwert zugeordnet und der Algorithmus ist quadratisch. Ich weiß nicht, was die Anforderungen des OP sind.

Wunder173

Sehen Sie sich meine Implementierung unten an und sagen Sie mir, wie quadratisch es im schlimmsten Fall ist.

Sammy

@ miracle173: Das ist nur Bequemlichkeit für die Notation. Ich kann die Hash-Tabelle als eine Reihe von Schlüssel-Wert-Paaren darstellen (was mathematisch gesehen tatsächlich so ist). Die tatsächliche Anordnung im Speicher ist für theoretische Details bezüglich der Komplexität nicht erforderlich. Hash-Funktionen sollen Kollisionen vermeiden, sofern genügend Keimentropie vorhanden ist. Ich antwortete mit dem, weil Juhos Antwort ein "sortiertes A" voraussetzt, was implizit die Komplexität O (n log (n)) und * NOT O (n) ergibt .

Juspreet Sandhu

@ manbearpig1 User Evil hat Ihrem Beitrag bereits einen Kommentar hinzugefügt, der Ihre Frage beantworten soll. Der schlechteste Fall der Hash-Tabellensuche ist O (n) und daher ist der schlechteste Fall des gesamten Algorithmus O (n ^ 2).

Wunder173

@JuspreetSandhu Usere Evil hat einer anderen Antwort einen Kommentar hinzugefügt , der das Problem mit den Hash-Funktionen erklärt.

Wunder173

-1

Beachten Sie, dass wir einen Wert in einem Python-Set in konstanter Zeit suchen können.

def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
        nums.add(num)
    return count

sammy
quelle

O (1)

$\mathcal O(1)$

O (n)

$\mathcal O(n)$

O (\log n)

$\mathcal O(\log n)$

O (n)

$\mathcal O(n)$

n

$n$

O (n^{2})

$\mathcal O(n^2)$