Ich versuche einen Algorithmus zu erstellen, der zwei benötigtArrays, S und T von n ganzen Zahlen und Ganzzahl k. Der Algorithmus prüft, ob die Arrays ganze Zahlen s und t haben, also s + t = k. (S in S und t in T.) Der Algorithmus soll eine Laufzeit von O (n log n) haben.
Ich habe versucht, an etwas zu denken, das das Array sortiertT und benutze die for-Schleife, um durch S zu gehen und binäre Suche zu verwenden, um zu sehen, ob ich eine Ganzzahl wie k - S [i] für jedes Element in S finde. Aber das wird immer eine Laufzeit größer als n log n haben, denke ich.
Nicht nach jemandem suchen, um den Code zu schreiben. Frag nur hier nach ein paar Ideen.
Antworten:
6 für die Antwort № 1Sortieren Sie die zwei Listen, das ist O (n log n).
Richte dann zwei Iteratoren ein. Ein Iterator beginnt am niedrigste Wert in S und geht weiter durch immer steigende Werte in S. Der andere Iterator beginnt bei der höchste Wert in T und iteriert durch immer kleiner werdende Werte.
Wiederhole das Folgende:
- wenn die aktuellen Werte zu einer Zahl größer als k, führe den T-Iterator weiter. Dies sollte die Summe verringern.
- wenn die aktuellen Werte zu einer Zahl kleiner als summieren k, schreite den S-Iterator voran. Dies sollte die Summe erhöhen.
- wenn die aktuellen Werte summieren k, dann mit Erfolg beenden.
Diese zweite Phase sollte höchstens 2 N fortschreiten und ist daher O (n). Also ist die Gesamtkomplexität O (n log n).
Dies hat die gleiche Komplexität wie wiederholte binäre Suche, aber dieser Algorithmus sollte schneller sein, insbesondere für große n.
3 für die Antwort № 2
Der Algorithmus, den Sie angegeben haben, hat tatsächlich Laufzeit O (n log n), vorausgesetzt, die Gesamtzahl der Elemente in beiden Arrays ist O (n). Sie können dies hier sehen:
- Sortiere eines der Arrays (O (n log n))
- Für jedes Element des anderen Arrays: (O (n) Iterationen)
- Führen Sie eine binäre Suche durch, um festzustellen, ob sich das Komplementärelement im anderen Array befindet (O (log n) -Zeit).
Der erste Schritt braucht Zeit O (n log n), und dieDer zweite Schritt besteht aus O (n) Iterationen eines O (log n) -Algorithmus, der also auch die Zeit O (n log n) benötigt. Da O (n log n) + O (n log n) = O (n log n) ist, läuft Ihr Algorithmus in der Zeit O (n log n). Es sieht also so aus, als hättest du genau den Algorithmus, nach dem du suchst!
Hoffe das hilft!
3 für die Antwort № 3
Sortieren beide die Arrays. Geh durch sie hinein Gegenteil Richtungen. Wenn die Summe der beiden Elemente kleiner als k ist, schreite den "ansteigenden" Zeiger, wenn er größer als k ist, schreite den abnehmenden Zeiger. Diese Methode ist möglicherweise etwas langsamer als das Sortieren nur eines der Arrays, aber der letzte Durchlauf ist definitiv schneller. Und wahrscheinlich kürzer, weil der Kopf- und der Schwanzteil der beiden Arrays übersprungen werden können (weggeschnitten).
2 für die Antwort № 4
Dein Ansatz scheint korrekt zu sein; Sortieren Sie zuerst die Arrays, dann zwei O (n log n) -Operationen und führen Sie dann n binäre Suchen durch, die jeweils O (log n) sind.
2 für die Antwort № 5
Die Sortierung ist O (n log n). Dann haben Sie für jedes O (n) erste Elemente eine O (log n) Suche nach einem passenden Element. Das klingt wie O (n log n) insgesamt (da O (f) + O (f) = O (f) für jede Funktion f).
0 für die Antwort № 6
Noch eine andere Methode: Speichern Sie eines der Arrays in einer Hashtabelle (O (N)). Mache einen linearen Durchlauf durch den anderen (O (N)) und suche für jedes Element nach k-elem in der Hashtabelle. Gesamtlaufzeit: 2 * O (N): = O (N). Profitieren!