PHP でデータ ストリーム内の K 番目に大きい要素を計算する方法

最小ヒープのプロパティを使用すると、最小ヒープのルート ノードはすべてのノードの中で最小でなければなりません。したがって、サイズ K 要素の最小ヒープを維持するだけで済みます。値が最小ヒープのルート ノードの値より大きい限り、ルート ノードの値が削除され、その値が最小ヒープに挿入されます。

#データ ストリーム内で K 番目に大きい要素を検索するクラスを設計します。これは並べ替え後の 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- の値を再検索する必要があるということです。フラッシュバック後は 6. 5, 3, 2、k = 2 の場合は 5 が返され、加算の場合は 1 が返されます。は最後に追加されますが結果には影響しませんが、add 7 の場合は先頭に追加され、戻り値は 6 になります。

問題解決のアイデア

最小ヒープを直接使用します。占有スペースを最小限に抑えるため、ヒープのサイズは k です。 minimum heap は最小値であり、これも望ましい結果です。 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 中国語 Web サイトの他の関連記事を参照してください。