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번째 요소의 값, 예를 들어 4개의 숫자 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!