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