Finden Sie bei einem gegebenen Array von n ganzen Zahlen und einer gegebenen Zahl X alle eindeutigen Paare von Elementen (a, b), deren Summation gleich X ist.
Das Folgende ist meine Lösung, es ist O (nLog (n) + n), aber ich bin nicht sicher, ob es optimal ist oder nicht.
int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
i++;
}
j--;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
j--;
}
}
}
while((arr[i] + arr[j]) <= sum && i < j)
sollte seinwhile( i < J && arr[i] + arr[j] <= sum )
. (ähnlich für die zweite Subloop)Antworten:
quelle
arr=[1,2,1,2,1,2,1,...]
. Für die Eindeutigkeit nach Wert scheint es, als würde eine andere Hash-Tabelle, die von einem Wertepaar verschlüsselt wird, den Trick tun. Immer noch eine schöne, kompakte, elegante Antwort. +1hash(K - arr[i]) != i
überprüfen irgendwie sowohl Vorhandensein und das Fehlen eines Spiels? Ich würde erwarten, dass es eine separate Überprüfung auf Anwesenheit gibt.Es gibt drei Ansätze für diese Lösung:
Die Summe sei T und n sei die Größe des Arrays
Ansatz 1:
Der naive Weg, dies zu tun, wäre, alle Kombinationen zu überprüfen (n wählen Sie 2). Diese erschöpfende Suche ist O (n 2 ).
Ansatz 2:
Ein besserer Weg wäre, das Array zu sortieren. Dies dauert O (n log n).
Verwenden Sie dann für jedes x in Array A die binäre Suche, um nach Tx zu suchen. Dies wird O (nlogn) dauern.
Die Gesamtsuche lautet also O (n log n).
Ansatz 3:
Der beste Weg wäre, jedes Element in eine Hash-Tabelle einzufügen (ohne zu sortieren). Dies nimmt O (n) als konstante Zeiteinfügung.
Dann können wir für jedes x einfach sein Komplement Tx nachschlagen, das O (1) ist.
Insgesamt beträgt die Laufzeit dieses Ansatzes O (n).
Sie können hier mehr verweisen. Danke.
quelle
Implementierung in Java: Verwenden des Codaddict-Algorithmus (möglicherweise etwas anders)
Für Eingabe =
{2,45,7,3,5,1,8,9}
und wenn Summe ist10
Ausgabepaare:
Einige Hinweise zur Lösung:
quelle
put(k-input[i], input[i])
(Codaddicts setzt den Index als nützlichen Wert). Was Sie geschrieben haben, kann vereinfacht werdenfor (i:input){ if (intSet.contains(sum-i) { print(i + "," + (sum-i) ); } else {intSet.add(i)}
Lösung in Java. Sie können alle String-Elemente zu einer ArrayList von Strings hinzufügen und die Liste zurückgeben. Hier drucke ich es gerade aus.
quelle
Python-Implementierung:
Ausgabe:
quelle
C ++ 11, Laufzeitkomplexität O (n):
quelle
Hier ist eine Lösung, die doppelte Einträge berücksichtigt. Es ist in Javascript geschrieben und setzt voraus, dass das Array sortiert ist. Die Lösung wird in O (n) -Zeit ausgeführt und verwendet außer Variablen keinen zusätzlichen Speicher.
Ich habe dies während eines Interviews für ein großes Unternehmen gelöst. Sie haben es genommen, aber nicht ich. Also hier ist es für alle.
Beginnen Sie auf beiden Seiten des Arrays und arbeiten Sie sich langsam nach innen, um sicherzustellen, dass Duplikate gezählt werden, falls vorhanden.
Es zählt nur Paare, kann aber überarbeitet werden
Genießen!
quelle
if(distI > distK) while(_arr[++i]==curI); else while(_arr[--k]==curK);
Auf)
Methodik: a + b = c, also suchen wir statt (a, b) nach a = c - b
quelle
Implementierung in Java: Verwenden des Codaddict-Algorithmus:
Ausgabe:
Wenn Sie auch doppelte Paare (z. B. 80,80) möchten, entfernen Sie einfach && (Integer) Mapping.get (ka [i])! = I aus der if-Bedingung und Sie können loslegen.
quelle
Ich habe gerade diese Frage auf HackerRank besucht und hier ist meine 'Objective C' -Lösung :
Hoffe es hilft jemandem.
quelle
Dies ist die Implementierung von O (n * lg n) unter Verwendung einer binären Suchimplementierung innerhalb einer Schleife.
quelle
In Python
quelle
Schöne Lösung von Codeaddict. Ich habe mir erlaubt, eine Version davon in Ruby zu implementieren:
Um doppelte Paare (1,5), (5,1) zuzulassen, müssen wir nur die
&& !result[sum-l]
Anweisung entfernenquelle
Hier ist Java-Code für drei Ansätze:
1. Mit Map O (n) kann auch HashSet hier verwendet werden.
2. Sortieren Sie das Array und suchen Sie dann mit BinarySearch nach dem Komplement O (nLog (n)).
3. Traditionelle BruteForce-Zwei-Schleifen O (n ^ 2)
quelle
Ein einfaches Programm in Java für Arrays mit eindeutigen Elementen:
quelle
Ein einfaches Java-Code-Snippet zum Drucken der folgenden Paare:
quelle
Eine andere Lösung in Swift: Die Idee ist, einen Hash zu erstellen, der Werte von (sum - currentValue) speichert und diesen mit dem aktuellen Wert der Schleife vergleicht. Die Komplexität ist O (n).
quelle
Meine Lösung - Java - Ohne Duplikate
quelle
Dies druckt die Paare und vermeidet Duplikate durch bitweise Manipulation.
quelle
Ich habe die Bitmanuplikation umgangen und nur die Indexwerte verglichen. Dies ist weniger als der Schleifeniterationswert (in diesem Fall i). Dadurch werden auch die doppelten Paare und doppelten Array-Elemente nicht gedruckt.
quelle
in C #:
quelle
Eine Lösung kann dies sein, aber nicht optimal (Die Komplexität dieses Codes ist O (n ^ 2)):
quelle
Eine einfache Python-Version des Codes, die eine Paarsumme von Null findet und geändert werden kann, um k zu finden:
Die Laufzeitkomplexität der Funktion ist ebenfalls O (n) und Space: O (n).
quelle
quelle
weniger als o (n) Lösung ist =>
quelle
Lösung in Python mit Listenverständnis
O (N 2 )
gibt auch zwei geordnete Paare an - (a, b) und (b, a)
quelle
I am not sure … Thanks for comments
). Sie könnten den Komplexitätsstich näher an O (n²) bezeichnen.Ich kann es in O (n) tun. Lassen Sie mich wissen, wann Sie die Antwort wollen. Beachten Sie, dass das Array einfach einmal ohne Sortierung usw. durchlaufen wird. Ich sollte auch erwähnen, dass es die Kommutativität der Addition ausnutzt und keine Hashes verwendet, sondern Speicher verschwendet.
mit System; using System.Collections.Generic;
/ * Ein O (n) -Ansatz existiert unter Verwendung einer Nachschlagetabelle. Der Ansatz besteht darin, den Wert in einem "Behälter" zu speichern, der leicht nachgeschlagen werden kann (z. B. O (1)), wenn es sich um einen Kandidaten für eine geeignete Summe handelt.
z.B,
Für jedes a [k] im Array setzen wir es einfach in ein anderes Array an der Stelle x - a [k].
Angenommen, wir haben [0, 1, 5, 3, 6, 9, 8, 7] und x = 9
Wir erstellen ein neues Array,
indiziert Wert
DANN sind nur diejenigen Werte von Bedeutung, die einen Index in der neuen Tabelle haben.
Wenn wir also 9 oder gleich erreichen, sehen wir, ob unser neues Array den Index 9 - 9 = 0 hat. Da wir wissen, dass alle darin enthaltenen Werte zu 9 addiert werden (beachten Sie, dass es in diesem Fall offensichtlich nur einen gibt 1 möglich, aber es kann mehrere Indexwerte enthalten, die wir speichern müssen).
Am Ende müssen wir uns also nur einmal durch das Array bewegen. Da die Addition kommutativ ist, erhalten wir alle möglichen Ergebnisse.
Wenn wir zum Beispiel 6 erreichen, erhalten wir den Index als 9 - 6 = 3 in unsere neue Tabelle. Da die Tabelle diesen Indexwert enthält, kennen wir die Werte.
Dies ist im Wesentlichen ein Kompromiss zwischen Geschwindigkeit und Speicher. * /
quelle
Javascript-Lösung:
quelle
https://github.com/clockzhong/findSumPairNumber
Ich habe es unter O (m + n) Komplexitätskosten für Zeit und Speicherplatz gemacht. Ich vermute, das ist der bisher beste Algorithmus.
quelle
int [] arr = {1,2,3,4,5,6,7,8,9,0};
var z = (von a in arr von b in arr wobei 10 - a == b neues {a, b} auswählen). ToList;
quelle