Dies ist das Problem, das ich gelöst habe (es ist ein Beispielproblem, kein echtes Problem):
%Vor%Gegebene N Zahlen, [N & lt; = 10 ^ 5] müssen wir die Gesamtpaare von zählen Zahlen, die einen Unterschied von K haben. [K & gt; 0 und K & lt; 1e9]
Eingabeformat: 1. Zeile enthält N & amp; K (ganze Zahlen). Die zweite Zeile enthält N Nummern des Satzes. Alle N-Nummern sind eindeutig verschieden. Ausgabeformat: Eine ganze Zahl, die die Anzahl der Paare von Zahlen angibt ein Diff K.
Ich habe bereits eine Lösung (und ich konnte sie nicht so gut optimieren, wie ich gehofft hatte). Gegenwärtig bekommt meine Lösung eine Punktzahl von 12/15 , wenn sie ausgeführt wird, und ich frage mich, warum ich nicht 15/15 bekomme (meine Lösung für ein anderes Problem war nicht annähernd so effizient, aber habe alle Punkte). Offensichtlich wird der Code mit "Mono 2.10.1, C # 4" ausgeführt.
Kann mir jemand eine bessere Möglichkeit vorstellen, dies weiter zu optimieren? Der VS-Profiler sagt, dass er den Aufruf von String.Split und Int32.Parse vermeiden sollte. Die Aufrufe von Int32.Parse können nicht vermieden werden, obwohl ich denke, dass ich das Tokening des Arrays optimieren könnte.
Meine aktuelle Lösung:
%Vor%Ihr Algorithmus ist immer noch O (n ^ 2), selbst bei der Sortierung und dem Früh-Out. Und selbst wenn Sie das O (n ^ 2) -Bit eliminiert haben, ist die Sortierung immer noch O (n lg n). Sie können ein O (n) -Algorithmus verwenden, um dieses Problem zu lösen. Hier ist eine Möglichkeit:
Angenommen, Sie haben S1 = { 1, 7, 4, 6, 3 } und die Differenz ist 2.
Konstruiere die Menge S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 } .
Die Antwort, die Sie suchen, ist die Kardinalität des Schnittpunkts von S1 und S2. Der Schnittpunkt ist {6, 3} , der zwei Elemente hat, also ist die Antwort 2.
Sie können diese Lösung in einer einzigen Codezeile implementieren, vorausgesetzt Sie haben eine Folge von Ganzzahlen sequence und ganzzahl difference :
Die Intersect-Methode erstellt eine effiziente Hash-Tabelle für Sie, die O (n) ist, um die Schnittmenge zu bestimmen.
Versuchen Sie es (Anmerkung, ungetestet):
Versuchen Sie im Grunde, die beiden Indizes um den K-Wert-Unterschied auseinander zu halten.
Sie sollten eine Reihe von Komponententests für Ihren Algorithmus schreiben und versuchen, Kantenfälle zu erstellen.
Damit können Sie es in einem einzigen Durchgang tun. Die Verwendung von Hash-Sets ist vorteilhaft, wenn viele Werte analysiert / geprüft werden müssen. Sie können auch einen Bloom-Filter in Kombination mit Hash-Sätzen verwenden, um Nachschlagevorgänge zu reduzieren.
Eigentlich ist das mit einer hashmap trivial zu lösen:
Zuerst gebe jede Zahl in einen Pseudo-Code namens hashmap: dict((x, x) for x in numbers) in "pythony";)
Jetzt iterieren Sie einfach jede Zahl in der Hashmap und prüfen, ob die Zahl + K in der Hashmap ist. Wenn ja, erhöhen Sie die Anzahl um eins.
Die offensichtliche Verbesserung der naiven Lösung besteht darin, NUR nach der höheren (oder niedrigeren) Grenze zu suchen, sonst erhalten Sie die doppelten Ergebnisse und müssen danach durch 2 dividieren - unbrauchbar.
Das ist O (N) zum Erzeugen der Hashmap beim Lesen der Werte in und O (N) beim Durchlaufen, also O (N) und etwa 8loc in Python (und es ist richtig, ich habe es gerade gelöst ;-) )
Tags und Links optimization c#