How to calculate the Kth largest element in a data stream in PHP

Using the properties of the minimum heap, the root node of the minimum heap must be the smallest of all nodes. Therefore, we only need to maintain a minimum heap of size K elements. As long as the value is greater than the value of the root node of the min-heap, the value of the root node is removed and the value is inserted into the min-heap.

#Design a class that finds the Kth largest element in the data stream. Note that it is the Kth largest element after sorting, not the Kth different element.

Your KthLargest class needs a constructor that accepts both an integer k and an integer array nums containing the initial elements in the data stream. Each time KthLargest.add is called, the Kth largest element in the current data stream is returned.

Example:

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

Explanation: You can assume that the length of nums ≥ k-1 and k ≥ 1.

Understand the meaning of the question

I didn’t understand this question at first. After reading it a few times, I figured it out. k is the designated position, and then a group of numbers, starting from the largest to a small arrangement, and then return the k-th element. The most basic consideration is that each add requires a sorting, and then re-find the value of the k-th element, such as 5, 3, 6, 2. After the flashback, it is 6. 5, 3, 2, then in the case of k = 2, 5 is returned, and then in the case of add 1, it is appended at the end, which does not affect the result. In the case of add 7, it is appended at the beginning, and the return value becomes 6.

Problem-solving ideas

Use the minimum heap directly. The size of the heap is k, so as to ensure the minimum space occupation. The root node of the minimum heap is the minimum value, which is also our desired result. PHP's SPL standard library has a minimum heap library, which directly inherits SplMinHeap in the code.

PHP implementation

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

Recommended learning: php video tutorial

The above is the detailed content of How to calculate the Kth largest element in a data stream in PHP. For more information, please follow other related articles on the PHP Chinese website!