PHP怎么計算數(shù)據(jù)流中的第K大的元素

這篇文章主要講解了“PHP怎么計算數(shù)據(jù)流中的第K大的元素”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“PHP怎么計算數(shù)據(jù)流中的第K大的元素”吧！

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

設(shè)計一個找到數(shù)據(jù)流中第K大元素的類（class）。注意是排序后的第K大元素，不是第K個不同的元素。

你的 KthLargest 類需要一個同時接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素。每次調(diào)用 KthLargest.add，返回當(dāng)前數(shù)據(jù)流中第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

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

理解題意

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

解題思路

直接使用最小堆，堆的大小為 k，這樣保證空間占用最小，最小堆的根節(jié)點是就是最小值，也是我們想要的結(jié)果。PHP 的 SPL 標(biāo)準(zhǔn)庫是有最小堆這個庫，直接在代碼中繼承 SplMinHeap 。

PHP 實現(xiàn)

class KthLargest extends SplMinHeap {
    /** 
    * @param Integer $k 
    * @param Integer[] $nums 
    */
    static $nums;
    public $k;
    function __construct($k, $nums) {
        $this->k = $k;
        // 遍歷初始化數(shù)組，分別插入堆中
        foreach ($nums as $v) {
            $this->add($v);
        }
    }
  
    /** 
    * @param Integer $val 
    * @return Integer 
    */
    function add($val) {
       // 維持堆的大小為k，當(dāng)堆還未滿時，插入數(shù)據(jù)。
        if ($this->count() < $this->k) {
            $this->insert($val);
        } elseif ($this->top() < $val) {
        // 當(dāng)堆滿的時候，比較要插入元素和堆頂元素大小。大于堆頂?shù)牟迦?。堆頂移除?
            $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怎么計算數(shù)據(jù)流中的第K大的元素”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對PHP怎么計算數(shù)據(jù)流中的第K大的元素這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！