Comment calculer le Kième plus grand élément d'un flux de données en PHP

En utilisant les propriétés du tas minimum, le nœud racine du tas minimum doit être le plus petit de tous les nœuds. Par conséquent, nous devons uniquement conserver un tas minimum d’éléments de taille K. Tant que la valeur est supérieure à la valeur du nœud racine du min-heap, la valeur du nœud racine est supprimée et la valeur est insérée dans le min-heap.

Concevez une classe qui trouve le Kième plus grand élément du flux de données. Notez qu'il s'agit du Kème élément le plus grand après le tri, et non du Kème élément différent.

Votre classe KthLargest a besoin d'un constructeur qui accepte à la fois un entier k et un tableau d'entiers nums contenant les éléments initiaux du flux de données. Chaque fois que KthLargest.add est appelé, le Kième plus grand élément du flux de données actuel est renvoyé.

Exemple :

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

Explication : Vous pouvez supposer que la longueur des nombres ≥ k-1 et k ≥ 1.

Comprendre le sens de la question

Je n'ai pas compris cette question au début, mais après l'avoir lu plusieurs fois, je l'ai compris. La considération de base est que chaque ajout nécessite un tri puis une nouvelle recherche. la valeur du k-ième élément, par exemple les quatre nombres 5, 3, 6, 2. Après le flashback, c'est 6, 5, 3, 2, puis k = 2 Ensuite, 5 est renvoyé, puis dans dans le cas de add 1, il est ajouté à la fin, ce qui n'affecte pas le résultat. Dans le cas de add 7, il est ajouté au début et la valeur de retour devient 6.

Idées de résolution de problèmes

Utilisez directement le tas minimum. La taille du tas est k, afin d'assurer l'occupation minimale de l'espace. Le nœud racine du tas minimum est la valeur minimale, qui est également le résultat. nous voulons. La bibliothèque standard SPL de PHP possède une bibliothèque de tas minimum, qui hérite directement de SplMinHeap dans le code.

Implémentation PHP

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); 
    */

Apprentissage recommandé : Tutoriel vidéo PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!