Bei zwei Arrays A[n] und B[m], wie finde ich das kleinste Fenster in A, das alle Elemente von B enthält.Das kleinste Fenster finden
Ich versuche, dieses Problem in O (n) Zeit zu lösen, aber ich habe ein Problem dabei. Gibt es einen gut bekannten Algorithmus oder eine Prozedur, um es zu lösen?
countLets Anruffenster 'minimal', wenn es nicht reduziert werden kann. D. h., Nach dem Erhöhen seines linken Randes oder Verringern seines rechten Randes ist es kein gültiges Fenster mehr (enthält nicht alle Elemente von B). Es gibt drei in Ihrem Beispiel: [0, 2], [2, 6], [6, 7]
Angenommen, Sie haben bereits das kleinste minimale Fenster gefunden [links, rechts]. ([0, 2] in Ihrem Beispiel) Jetzt schieben wir es einfach nach rechts.
// count[x] tells how many times number 'x'
// happens between 'left' and 'right' in 'A'
while (right < N - 1) {
// move right border by 1
++right;
if (A[right] is in B) {
++count[A[right]];
}
// check if we can move left border now
while (count[A[left]] > 1) {
--count[A[left]];
++left;
}
// check if current window is optimal
if (right - left + 1 < currentMin) {
currentMin = right - left + 1;
}
}
Dieses Verschieben funktioniert, weil verschiedene "minimale" Fenster einander nicht enthalten können.
Im Wesentlichen das gleiche wie meiner, außer dass Sie nicht angegeben haben, wie 'count' funktioniert, während mir schwerer zu folgen ist. – Artelius
Weeeell, es kann nur ein Array sein, wenn die Zahlen in B nicht zu groß sind :) aber du hast recht, es ist das gleiche. –
Vielen Dank Artelius und Nikita – mousey
Wenn m > n, A können nicht alle Elemente der B enthalten (und damit haben wir eine O(1) Lösung).
Ansonsten:
B zu der Sequenz {0..m-1} (dies ist seit O(n)).C[m], um das Vorkommen der Mitglieder von B (initialisiert auf 0) im aktuellen Fenster zu zählen.Erstellen Sie eine Variable z, um die Anzahl der 0 Elemente von C zu zählen (initialisieren auf m).
Variablen erstellen s und e den Beginn und das Ende des aktuellen Fensters
e < n bezeichnen:
z ungleich Null ist, erhöht e und aktualisieren C und z. O(1)s und aktualisieren Sie C und z. O(1)Die while-Schleife gezeigt werden kann, nicht mehr als 2n Iterationen haben. Also die ganze Sache ist O(n), denke ich.
+1 Ja, genau wie meine :) –
Was ist "Fenster" in diesem Kontext? –
Beispiel: A = {1,3,2,4,5,6,1,2} B = {1,2} Das kleinste Fenster ist von Index 6 bis 7. – mousey
Muss das Fenster alle Elemente von B enthalten ? Ist die Reihenfolge wichtig? Oder, in Ihrem Beispiel, stellen die Positionen 2..6 auch ein Fenster dar, das B enthält? –