当前位置:首页 > PHP教程 > php高级应用 > 列表

php数据流中第K大元素的计算方法及代码分析

发布:smiling 来源: PHP粉丝网  添加日期:2022-05-08 10:40:33 浏览: 评论:0 

在本篇文章里小编给大家整理了一篇关于php数据流中第K大元素的计算方法及代码分析内容,有兴趣的朋友们可以学习下。

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

计算方法

1、直接使用最小堆,堆的大小为 k,这样保证空间占用最小,最小堆的根节点是就是最小值,也是我们想要的结果。

2、php的spl标准库是有最小堆这个库,直接在代码中继承SplMinHeap。

实例:

  1. class KthLargest extends SplMinHeap { 
  2.  
  3.     /** 
  4.     * @param Integer $k 
  5.     * @param Integer[] $nums 
  6.     */ 
  7.     static $nums
  8.     public $k
  9.     function __construct($k$nums) { 
  10.         $this->k = $k
  11.         // 遍历初始化数组,分别插入堆中 
  12.         foreach ($nums as $v) { 
  13.             $this->add($v); 
  14.         } 
  15.     } 
  16.      
  17.     * @param Integer $val 
  18.     * @return Integer 
  19.     function add($val) { 
  20.        // 维持堆的大小为k,当堆还未满时,插入数据。 
  21.         if ($this->count() < $this->k) { 
  22.             $this->insert($val); 
  23.         } elseif ($this->top() < $val) { 
  24.         // 当堆满的时候,比较要插入元素和堆顶元素大小。大于堆顶的插入。堆顶移除。 
  25.             $this->extract(); 
  26.         return $this->top(); 
  27.     }} 
  28.     * Your KthLargest object will be instantiated and called as such: 
  29.     * $obj = KthLargest($k$nums); 
  30.     * $ret_1 = $obj->add($val); 

实例扩展:

  1. class KthLargest { 
  2.     /** 
  3.      * @param Integer $k 
  4.      * @param Integer[] $nums 
  5.      */ 
  6.     static $nums
  7.     public $k
  8.     function __construct($k$nums) { 
  9.         $this->k = $k
  10.         $this->nums = $nums
  11.     } 
  12.     
  13.     /** 
  14.      * @param Integer $val 
  15.      * @return Integer 
  16.      */ 
  17.     function add($val) { 
  18.         array_push($this->nums, $val); 
  19.         rsort($this->nums); 
  20.         return $this->nums[$this->k - 1]; 
  21.     } 

第一个思路,时间超限的原因是每次都要对$this->nums这个数组,进行重新排序,上次已经排序好的,还要再重新排一次,浪费时间。所以,下面的解法是,每次只保存,上次排序完的前k个元素。这次的进行排序的次数就减少了。时间也减少了。

  1. class KthLargest { 
  2.     /** 
  3.      * @param Integer $k 
  4.      * @param Integer[] $nums 
  5.      */ 
  6.     static $nums
  7.     public $k
  8.     function __construct($k$nums) { 
  9.         $this->k = $k
  10.         $this->nums = $nums
  11.     } 
  12.     
  13.     /** 
  14.      * @param Integer $val 
  15.      * @return Integer 
  16.      */ 
  17.     function add($val) { 
  18.         array_push($this->nums, $val); 
  19.         rsort($this->nums); 
  20.         $this->nums = array_slice($this->nums, 0, $this->k); 
  21.           
  22.         return $this->nums[$this->k - 1]; 
  23.     } 
  24. }

Tags: php数据流 php第K大元素

分享到: