php 데이터 흐름 에서 K 대 원소 의 계산 방법 및 코드 분석

데이터 흐름 에서 K 대 요 소 를 찾 는 클래스(class)를 설계 합 니 다.주 의 는 정렬 된 K 의 큰 요소 이지 K 의 다른 요소 가 아 닙 니 다.
계산 방법
1.가장 작은 무 더 기 를 직접 사용 하고 쌓 인 크기 는 k 이다.이렇게 하면 공간 이 가장 적 게 차지 하고 가장 작은 뿌리 노드 는 가장 작은 값 이자 우리 가 원 하 는 결과 이다.
2.phop 의 spl 표준 라 이브 러 리 는 이 라 이브 러 리 를 최소 화하 고 코드 에서 SplMinHeap 를 직접 계승 합 니 다.
실례

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();
        return $this->top();
    }}
    * Your KthLargest object will be instantiated and called as such:
    * $obj = KthLargest($k, $nums);
    * $ret_1 = $obj->add($val);

인 스 턴 스 확장:

class KthLargest {
    /**
     * @param Integer $k
     * @param Integer[] $nums
     */
    static $nums;
    public $k;
    function __construct($k, $nums) {
        $this->k = $k;
        $this->nums = $nums;
    }
  
    /**
     * @param Integer $val
     * @return Integer
     */
    function add($val) {
        array_push($this->nums, $val);
        rsort($this->nums);
        return $this->nums[$this->k - 1];
    }
}

첫 번 째 사고,시간 이 제한 을 초과 한 이 유 는 매번$this->nums 라 는 배열 에 대해 재 정렬 을 해 야 하기 때 문 입 니 다.지난번 에 이미 정렬 한 것 은 다시 한 번 배열 해 야 하기 때문에 시간 을 낭비 합 니 다.그래서 다음 해법 은 매번 저장 하고 마지막 으로 정렬 한 앞의 k 개 요소 만 저장 하 는 것 입 니 다.이번 의 정렬 횟수 는 줄 어 들 었 다.시간 도 줄 었 고

class KthLargest {
    /**
     * @param Integer $k
     * @param Integer[] $nums
     */
    static $nums;
    public $k;
    function __construct($k, $nums) {
        $this->k = $k;
        $this->nums = $nums;
    }
  
    /**
     * @param Integer $val
     * @return Integer
     */
    function add($val) {
        array_push($this->nums, $val);
        rsort($this->nums);
        $this->nums = array_slice($this->nums, 0, $this->k);
        
        return $this->nums[$this->k - 1];
    }
}

phop 데이터 흐름 에서 K 대 요소 의 계산 방법 및 코드 분석 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.phop 데이터 흐름 에서 K 대 요소 의 계산 방법 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 지원 을 바 랍 니 다!