Problem: Bei einem Eingabearray mit Ganzzahlen der Größe n und einem Abfragearray mit Ganzzahlen der Größe k finde das kleinste Fenster des Eingabearrays, das alle Elemente des Abfragearrays enthält und auch in der gleichen Reihenfolge.
>Ich habe versucht unten Ansatz.
%Vor%Sucht die Position aller Abfrage-Array-Elemente in inputArray.
%Vor%Ich habe folgendes Wörterbuch
bekommenNun möchte ich den folgenden Schritt ausführen, um ein minimales Fenster zu finden
Vergleiche int 2 Position mit int 1 Position. Als (6-3) & lt; (6-1) .. Also werde ich 3, 6 in einer hashmap speichern.
Vergleicht die Position von int 1 und int 7 wie oben.
Ich kann nicht verstehen, wie ich zwei aufeinanderfolgende Werte eines Wörterbuchs vergleichen werde. Bitte helfen Sie.
Der Algorithmus:
Speichern Sie für jedes Element im Abfragearray in einer Map M (V → (I, P)), V ist das Element, I ist ein Index in das Eingabearray, P ist die Position im Abfragearray. (Der Index in das Eingabearray für einige P ist der größte, so dass die Abfrage [0..P] eine Untersequenz der Eingabe [I..curr])
Iteriere durch das Array.
Wenn der Wert der erste Begriff im Abfragearray ist: Speichern Sie den aktuellen Index als I.
Else: Speichere den Wert des Index des vorherigen Elements in dem Abfrage-Array, z. M[currVal].I = M[query[M[currVal].P-1]].I .
Wenn der Wert der letzte Begriff ist: Überprüfen Sie, ob [I..curr] ein neues Bestes ist.
Komplexität
Die Komplexität davon ist O (N) , wobei N die Größe des Eingabearrays ist.
NB.
Dieser Code erwartet, dass keine Elemente im Abfragearray wiederholt werden. Um dies zu berücksichtigen, können wir eine Karte M (V → listOf ((I, P))) verwenden. Dies ist O (N hC (Q)), wobei hC (Q) die Anzahl der Modi für das Abfragearray ist.
Noch besser wäre es, M (V → listOf ((linkedList (I), P))) zu verwenden. Wenn wiederholte Elemente nacheinander im Abfragearray auftreten, verwenden wir eine verkettete Liste. Die Aktualisierung dieser Werte wird dann zu O (1). Die Komplexität ist dann O (N hC (D (Q))), wobei D (Q) Q ist mit aufeinanderfolgenden zusammengesetzten Termen.
Implementierung
Die Beispiel-Java-Implementierung ist hier verfügbar. Dies funktioniert nicht für wiederholte Elemente im Abfragearray, noch für eine Fehlerüberprüfung usw.
Ich sehe nicht, wie Sie HashSet und Dictionary dabei helfen können. Wäre ich mit diesem Problem konfrontiert, würde ich es ganz anders machen.
Eine Möglichkeit, dies zu tun (nicht die effizienteste Methode), ist unten gezeigt. Dieser Code macht die Annahme, dass queryArray mindestens zwei Elemente enthält.
Mit etwas Arbeit könnte dies effizienter gemacht werden. Beispiel: Wenn 'queryArray' [1, 2, 3] enthält und inputArray [1, 7, 4, 9, 1, 3, 6, 4, 1, 8, 2, 3] enthält, findet der obige Code drei Übereinstimmungen (beginnend bei den Positionen 0, 4 und 8). Etwas intelligenterer Code könnte bestimmen, dass, wenn die 1 an Position 4 gefunden wird, da keine 2 davor gefunden wurde, jede Sequenz, die an der ersten Position beginnt, länger als die Sequenz an Position 4 beginnend und daher kurz ist - Schalten Sie die erste Sequenz ein und beginnen Sie an der neuen Position. Das macht den Code allerdings etwas komplizierter.
Sie möchten kein HashSet, sondern einen (sortierten) Baum oder ein Array als Wert im Wörterbuch; Das Wörterbuch enthält Zuordnungen von Werten, die Sie im Eingabearray finden, zu der (sortierten) Liste von Indizes, in denen dieser Wert erscheint.
Dann machst du folgendes
(Beachten Sie, dass der "niedrigste Eintrag größer" eine Operation ist, die mit sortierten Bäumen geliefert wird, oder über eine binäre Suche in einem sortierten Array gefunden werden kann.)
Die Komplexität davon ist ungefähr O(M*n*log n) , wobei M die Länge der Abfrage und n die durchschnittliche Anzahl der Indizes angibt, bei denen ein bestimmter Wert im Eingabearray erscheint. Sie können die Strategie ändern, indem Sie den Wert des Abfragearrays auswählen, der am wenigsten häufig für den Startpunkt erscheint und von dort aus hoch und runter geht. Wenn es k dieser Einträge gibt ( k & lt; = n ), dann ist die Komplexität O(M*k*log n) .
Nachdem Sie alle Positionen (Indizes) im inputArray erhalten haben:
%Vor% Ich verwende eine Rekursion, um alle möglichen Pfade zu erhalten. [0- & gt; 5- & gt; 7] [0- & gt; 6- & gt; 7] [2- & gt; 5- & gt; 7] [2- & gt; 6- & gt; 7]. Die Summe ist 2 * 2 * 1 = 4 mögliche Pfade. Offensichtlich ist derjenige, der Min(Last-First) hat, der kürzeste Pfad (kleinstes Fenster), diese Zahlen in der Mitte des Pfades sind nicht wichtig. Hier kommt der Code.
Nach den Datenstrukturen ist hier Main .
FindAllIndexes ist eine Erweiterungsmethode, die dabei hilft, alle Indizes zu finden.
Die Rekursionsmethode:
%Vor% Endlich kann eine Schleife von results das Min(Last-First) Ergebnis (kürzestes Fenster) finden.
Algorithmus:
c # Implementierung:
Holen Sie zuerst alle Indizes in das inputArray aller queryArray-Werte und sortieren Sie sie aufsteigend nach Index.
%Vor%Als nächstes benutze jeden Index (x) als Ausgangspunkt, um den ersten höheren Index (y) zu finden, so dass das Segment inputArray [x-y] alle queryArray-Werte enthält.
%Vor%Behalten Sie jetzt nur die Segmente bei, in denen die queryArray-Elemente angeordnet sind.
%Vor%Ordnen Sie abschließend die Segmente nach ihrer Länge ansteigend zu. Das erste Segment im Ergebnis ist das kleinste Fenster in inputArray, das alle queryArray-Werte in der Reihenfolge queryArray enthält.
%Vor%teste es mit
%Vor%Ausgabe:
%Vor%Danke euch allen für eure Beiträge. Ich habe meinen Code ein wenig geändert und finde es funktioniert. Obwohl es nicht sehr effizient ist, aber ich bin glücklich, mit meinem Kopf zu lösen :). Bitte geben Sie Ihr Feedback
Hier ist meine Pair-Klasse mit Nummer und Position als Variable
%Vor%Hier ist eine Methode, die die Liste aller Paare zurückgibt.
%Vor%Hier ist die Codezeile in der Hauptmethode
%Vor%Tags und Links algorithm c# data-structures collections