PHP如何計算資料流中的第K大的元素

利用最小堆的性質，此最小堆的根結點一定是所有結點中最小的。所以，我們只需要維護K個元素大小的最小堆。只要是大於最小堆的根結點的值，就移除該根結點的值，把該值插入最小堆中。

設計一個找到資料流中第K大元素的類別（class）。注意是排序後的第K大元素，不是第K個不同的元素。

你的 KthLargest 類別需要同時接收整數 k 和整數陣列nums 的建構器，它包含資料流中的初始元素。每次呼叫 KthLargest.add，返回目前資料流中第K大的元素。

範例：

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

說明: 你可以假設 nums 的長度≥ k-1 且k ≥ 1。

理解題意

最開始沒理解這題，讀了幾遍明白了，k 是指定的位置，然後一組數，按從大到小排列，然後返回第k 個元素，最基礎考慮是每次add 都需要一次排序，然後重新查找第k 個元素的值，例如5，3，6，2 四個數，倒敘之後是6， 5，3，2，則k = 2 的情況下，返回5，然後add 1的情況，追加在最末尾，不影響結果，add 7 的情況，追加在最開頭，返回值變成6。

解題想法

直接使用最小堆，堆的大小為k，這樣保證空間佔用最小，最小堆的根節點是就是最小值，也是我們想要的結果。 PHP 的 SPL 標準函式庫是有最小堆這個函式庫，直接在程式碼中繼承 SplMinHeap 。

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

推薦學習：php影片教學

#

以上是PHP如何計算資料流中的第K大的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！