設(shè)計一個找到數(shù)據(jù)流中第K大元素的類（class）。注意是排序后的第K大元素，不是第K個不同的元素。
計算方法
1、直接使用最小堆，堆的大小為 k，這樣保證空間占用最小，最小堆的根節(jié)點是就是最小值，也是我們想要的結(jié)果。
2、php的spl標準庫是有最小堆這個庫，直接在代碼中繼承SplMinHeap。
實例
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，當堆還未滿時，插入數(shù)據(jù)。
if ($this->count() $this->k) {
$this->insert($val);
} elseif ($this->top() $val) {
// 當堆滿的時候，比較要插入元素和堆頂元素大小。大于堆頂?shù)牟迦?。堆頂移除?
$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這個數(shù)組，進行重新排序，上次已經(jīng)排序好的，還要再重新排一次，浪費時間。所以，下面的解法是，每次只保存，上次排序完的前k個元素。這次的進行排序的次數(shù)就減少了。時間也減少了。
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];
}
}
到此這篇關(guān)于php數(shù)據(jù)流中第K大元素的計算方法及代碼分析的文章就介紹到這了,更多相關(guān)php數(shù)據(jù)流中第K大元素的計算方法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
