k-tes kleinstes Element im Gleitsegment

Question

Betrachten Sie ein Array $a[1\ldots n]$ und ein anderes Array $l = a[0]$(Ursprünglicher Wert). In jeder Runde können wir dem Array das nächste Element hinzufügen$l$oder entfernen Sie das erste Element aus dem Array $l$. Fe nach der ersten Iteration könnte es leer sein oder werden$a[0, 1]$. Wir wollen das k-te kleinste Element bei jeder Iteration im Array finden$l$.

Zuallererst, wenn Größe von $l$ ist weniger als $k$Die Antwort ist nein'. Betrachten wir einen interessanteren Fall.

Ich habe mich für zwei Haufen entschieden (einen Min- und einen Max-Haufen).

Max Heap enthält alle k-ten kleinsten Elemente aus $a[l..r]$und min heap enthält Elemente, die größer als das k-te kleinste Element sind. Dann ist die Antwort der Kopf von max-heap (wir können es in O (1) nehmen).

Aber es gibt ein kleines Problem. Was ist, wenn Sie dies berücksichtigen müssen?$a[l+1 .. r]$(Also müssen wir nach links drücken). Jetzt natürlich wenn$r - l < k$Die Antwort lautet "Nein", aber was sollen wir sonst tun? Ich dachte, wir sollten Folgendes tun: wenn$a[l] > maxheap[0]$dann ändert sich die Antwort nicht (weil wir ein Element löschen, das größer als das k-te kleinste Element ist), aber was sollen wir mit unseren Haufen tun? Leider kann ich nicht in Heap nach Position löschen (es dauert lange). Das Beste, was wir tun können, ist, den Wurzelknoten in O (log n) zu löschen. Wie soll ich sie beeinflussen?

Answer 1

Pflegen Sie einen AVL-Baum $B$ das speichert die Elemente in $l$. Zusätzlich für jedes Element$a$ im $l$, behalte einen Zeiger $p_a$ zum entsprechenden Knoten in $B$.

• Wenn ein Element $x$ wird hinzugefügt $l$Fügen Sie dann einfach einen neuen Knoten ein $v$ Darstellen $x$ in $B$ und mache $p_x$ zeigen auf $v$.

• Wenn das erste Element $y$ von $l$ muss entfernt werden, löschen (der Knoten, auf den gezeigt wird) $p_y$ von $B$.

• Um das zu melden $k$-minimales Element in $l$Suchen Sie einfach nach dem minimalen Element in $B$(dh derjenige, der im Knoten ganz links gespeichert ist). Dies kann in erfolgen$O(\log n)$ Zeit durch einfaches Halten in jedem Knoten $v$, die Größe des Teilbaums von $B$ verwurzelt in $v$.

Durch die Kombination der oben genannten Vorgänge wird jede Runde Ihres Problems erforderlich $O(\log(1 + |l|)) = O(\log n)$ Zeit.