Du kannst es in O (n ^ 2) machen. Funktioniert gut mit doppelten und negativen Zahlen.
Bearbeiten wie Andre im Kommentar bemerkte, ist die Zeit mit der Verwendung von Hash, was "schlimmsten Fall" hat (obwohl es weniger wahrscheinlich ist, als in einer Lotterie zu gewinnen). Sie können aber auch die Hashtabelle durch einen ausgeglichenen Baum (TreeMap in Java) ersetzen und erhalten eine stabile O (n ^ 2 * log (n)) Lösung.
Hashtable sums speichert alle möglichen Summen zweier verschiedener Elemente. Für jede Summe S gibt es das Paar der Indizes i und j zurück, so dass a[i] + a[j] == S und i != j . Aber anfangs ist es leer, wir werden es unterwegs auffüllen.
Sagen wir, X = a[1] + a[3] + a[7] + a[10] . Diese Summe wird gefunden, wenn i = 7 , j = 10 und rest = a[1] + a[3] (die Indizes 1 und 3 werden aus dem Hash ermittelt)
Missbrauch der Tatsache, dass kein Speicherbeschränkung angegeben ist. Und mit dem üblichen "Teile und herrsche" Ansatz.
Die Anzahl aller Permutationen für 4 Teilmengen ist C (n, 4) und ist O (n ^ 4) . Die Anzahl aller Permutationen für 2 Zahlen ist C (n, 2) und ist O (n ^ 2). O (n ^ 2) scheint für die Aufgabe in Ordnung zu sein.
A mit n elements, X . B mit n ^ 2 Elementen (erinnere dich auch an die Teilmengen). Wir bezeichnen als S[B[i]] die Teilmenge (bestehend aus den zwei Zahlen), deren Summe B[i] ist. B , O (n ^ 2 * log (n ^ 2)). Durchlaufen Sie das Array B (O (n ^ 2)) i = [0,n^2) und die Schnellsuche O(log(n^2)) = O(log(n)) darin für den Wert (X - B[i]) . Es könnte einige von ihnen geben (aber nicht mehr als n ^ 2).
4.1. Gehe durch alle Elemente mit dem Wert (X - B[i]) und verwende den Index k .
4.2. Überspringen Sie die Elemente B[k] , wobei S[B[k]] sich mit S[B[i]] überschneidet. Der Schnittpunkt zweier Mengen mit zwei Zahlen kann in O (1) berechnet werden.
4.3 Wenn k der Index ein Element ist, in dem sich B[i] + B[k] == X und S[B[k]] nicht mit S[B[i]] überschneiden, dann ist die Summe der Mengen S[B[k]] und S[B[i]] die vier gesuchten Zahlen.
Leistung ist: O (n ^ 2 + n ^ 2 * log (n ^ 2) + n ^ 2 * log (n ^ 2)) = O (n ^ 2 * log (n ^ 2)) = O (n ^ 2 * log (n))
In Schritt vier, wenn wir über die mehreren übereinstimmenden Elemente von B mit der verschachtelten Schleife iterieren. Die Gesamtzahl der Iterationen der beiden verschachtelten Schleifen ist jedoch durch die |B| begrenzt, die O (n ^ 2) ist. Die Schnellsuche ist nicht die übliche Variante, sondern diejenige, die das passende Element mit dem niedrigsten Index findet. (Alternativ kann man die übliche bsearch verwenden und da wir in der Mitte gelandet sein könnten, benutzen Sie zwei benachbarte Schleifen, die Elemente in beide Richtungen prüfen.)
1) Erstellen Sie ein Array aller möglichen Paarsummen [O (N ^ 2)]
2) Sortiere dieses Array in aufsteigender Reihenfolge [O (N ^ 2 * Log N)]
3) Dieses Problem reduziert sich jetzt auf das Finden von 2 Zahlen in einem sortierten Array, die zu einer gegebenen Zahl X in linearer Zeit summieren. Verwenden Sie 2 Zeiger: ein LOW-Zeiger beginnend mit dem niedrigsten Wert und ein HIGH-Zeiger beginnend mit dem höchsten Wert. Wenn die Summe zu niedrig ist, fahren Sie mit LOW fort. Wenn die Summe zu hoch ist, fahren Sie mit HIGH (rückwärts) fort. Irgendwann werden sie dieses Paar finden oder sich kreuzen (das kann leicht bewiesen werden). Dieser Prozess benötigt eine lineare Zeit in der Größe des Arrays, d. H. O (N ^ 2)
Dies ergibt eine Gesamtzeit von O (N ^ 2 * logN) wie erforderlich.
HINWEIS : Diese Methode kann verallgemeinert werden, um den Fall von M Zahlen in O (M * N ^ (M / 2) * log N) -Zeit zu lösen.
- BEARBEITEN -
Tatsächlich ist meine Antwort der Antwort von Dummy00001 sehr ähnlich, außer der endgültigen Suche, bei der ich eine schnellere Methode verwende (obwohl die Gesamtkomplexität die gleiche ist ...)
Klingt für mich wie Hausaufgaben. Aber hier wäre, was ich tun würde.
Sortieren Sie zuerst die Zahlen (es gibt Ihr n * log (n)).
Erstellen Sie nun Zeiger auf die Liste, initialisieren Sie sie mit den ersten 4 Zahlen. Sobald Sie das haben, überprüfen Sie die Summe Ihrer 4 aktuellen Nummern mit der Summe. Es sollte kleiner oder gleich Ihrer Suchsumme sein (wenn nicht, können Sie früher aufhören). Jetzt müssen Sie nur noch den Rest der Liste durchlaufen und die Zeiger durch den aktuellen Wert in der Liste ersetzen. Dies muss nur einmal (oder wirklich im schlimmsten Fall 4 mal) geschehen, also gibt es dein anderes n, was n ^ 2 * log (n) macht
Sie müssen einige Logik im Auge behalten, um zu wissen, ob Sie über oder unter Ihrer Summe sind und was Sie als nächstes tun sollen, aber ich überlasse das als Hausaufgabe.
Ich werde deine Frage nicht vollständig beantworten, da ich denke, dass es Hausaufgaben sind und denke, dass dies leicht gemacht wird. Aber ich denke, dass ich weiß, warum Sie Schwierigkeiten mit einer Antwort haben, also werde ich Ihnen ein wenig helfen.
Zuerst sollten Sie in Rekursion schauen. Das bedeutet, eine Funktion von sich selbst aus aufrufen.
Zweitens sollten Sie eine Hilfsfunktion verwenden, die von der Funktion aufgerufen wird, die Sie schreiben möchten. Diese Funktion sollte als Argumente dienen: - Eine Reihe von Zahlen - Die Länge des Arrays - Den Wert, den Sie suchen, finden Sie die Mitglieder, die zusammenfassen - Die Anzahl der Mitglieder des Arrays, die Sie zusammenfassen möchten
Diese Funktion wird von Ihrer anderen Funktion aufgerufen und eine 4 für das letzte Argument übergeben. Es wird sich dann selbst nennen, indem es die Argumente anpasst, während es versucht, durch partielles Versuch und Irrtum Ergebnisse zu finden.
Ich habe eine O (N ^^ 2) Laufzeitfunktion geschrieben, die keine Hashtabellen verwendet, aber negative Zahlen behandelt und doppelte Zahlen scheinbar OK. Ich handle mit negativen Zahlen in einem Integer-Array, indem ich eine große positive Zahl (z. B. 100) zu allen Ganzzahlen in dem Array hinzufüge. Dann passe ich das Ziel um target += (4 * 100) an. Wenn ich dann ein Ergebnis finde, subtrahiere ich die 100 von den ganzen Zahlen im Ergebnis. Hier ist mein Code und Testfälle: Bitte lassen Sie mich wissen, ob diese (N ^^ 2) Zeit Komplexität.
Dieses Problem kann als eine Variante der Pascal-Identität angesehen werden,
Hier ist der vollständige Code:
Bitte entschuldigen Sie, wie der Code in Java ist:
%Vor%}
Beispieleingabe :
%Vor%Ausgabe: :
%Vor%