So berechnen Sie das K-te größte Element in einem Datenstrom in PHP

Unter Verwendung der Eigenschaften des minimalen Heaps muss der Wurzelknoten des minimalen Heaps der kleinste aller Knoten sein. Daher müssen wir nur einen minimalen Heap von Elementen der Größe K aufrechterhalten. Solange der Wert größer ist als der Wert des Wurzelknotens des Min-Heaps, wird der Wert des Wurzelknotens entfernt und der Wert in den Min-Heap eingefügt.

Entwerfen Sie eine Klasse, die das K-te größte Element im Datenstrom findet. Beachten Sie, dass es sich nach der Sortierung um das K-te größte Element und nicht um das K-te andere Element handelt.

Ihre KthLargest-Klasse benötigt einen Konstruktor, der sowohl eine Ganzzahl k als auch ein ganzzahliges Array nums akzeptiert, das die Anfangselemente im Datenstrom enthält. Bei jedem Aufruf von KthLargest.add wird das K-tgrößte Element im aktuellen Datenstrom zurückgegeben.

Beispiel:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Erläuterung: Sie können davon ausgehen, dass die Länge von Zahlen ≥ k-1 und k ≥ 1 ist.

Verstehen Sie die Bedeutung der Frage

Ich habe diese Frage zunächst nicht verstanden, aber nachdem ich sie ein paar Mal gelesen habe, ist mir klar geworden, dass jede Hinzufügung eine Sortierung und dann eine erneute Suche erfordert der Wert des k-ten Elements, zum Beispiel die vier Zahlen 5, 3, 6, 2. Nach dem Rückblick ist es 6, 5, 3, 2, dann ist k = 2. Als nächstes wird 5 zurückgegeben und dann in Im Fall von add 1 wird es am Ende angehängt, was keinen Einfluss auf das Ergebnis hat. Im Fall von add 7 wird es am Anfang angehängt und der Rückgabewert wird 6.

Ideen zur Problemlösung

Verwenden Sie den minimalen Heap direkt. Die Größe des Heaps beträgt k, um sicherzustellen, dass der Wurzelknoten des minimalen Heaps der Mindestwert ist wir wollen. Die SPL-Standardbibliothek von PHP verfügt über eine minimale Heap-Bibliothek, die SplMinHeap direkt im Code erbt.

PHP-Implementierung

class KthLargest extends SplMinHeap {
    /** 
    * @param Integer $k 
    * @param Integer[] $nums 
    */
    static $nums;
    public $k;
    function __construct($k, $nums) {
        $this->k = $k;
        // 遍历初始化数组，分别插入堆中
        foreach ($nums as $v) {
            $this->add($v);
        }
    }
  
    /** 
    * @param Integer $val 
    * @return Integer 
    */
    function add($val) {
       // 维持堆的大小为k，当堆还未满时，插入数据。
        if ($this->count() < $this->k) {
            $this->insert($val);
        } elseif ($this->top() < $val) {
        // 当堆满的时候，比较要插入元素和堆顶元素大小。大于堆顶的插入。堆顶移除。
            $this->extract();
            $this->insert($val);
        }
        return $this->top();
    }}
    /** 
    * Your KthLargest object will be instantiated and called as such: 
    * $obj = KthLargest($k, $nums); 
    * $ret_1 = $obj->add($val); 
    */

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo berechnen Sie das K-te größte Element in einem Datenstrom in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!