• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
麻辣鸡翅 显示全部楼层 发表于 2021-8-14 15:07:06 |阅读模式 打印 上一主题 下一主题
计划一个找到数据流中第K大元素的类(class)。留意是排序后的第K大元素,不是第K个差别的元素。
盘算方法

1、直接使用最小堆,堆的巨细为 k,这样保证空间占用最小,最小堆的根节点是就是最小值,也是我们想要的结果。
2、php的spl标准库是有最小堆这个库,直接在代码中继承SplMinHeap。
实例
  1. class KthLargest extends SplMinHeap {
  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.         // 遍历初始化数组,分别插入堆中
  11.         foreach ($nums as $v) {
  12.             $this->add($v);
  13.         }
  14.     }
  15.    
  16.     * @param Integer $val
  17.     * @return Integer
  18.     function add($val) {
  19.        // 维持堆的大小为k,当堆还未满时,插入数据。
  20.         if ($this->count() < $this->k) {
  21.             $this->insert($val);
  22.         } elseif ($this->top() < $val) {
  23.         // 当堆满的时候,比较要插入元素和堆顶元素大小。大于堆顶的插入。堆顶移除。
  24.             $this->extract();
  25.         return $this->top();
  26.     }}
  27.     * Your KthLargest object will be instantiated and called as such:
  28.     * $obj = KthLargest($k, $nums);
  29.     * $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.     }
  22. }
复制代码
第一个思路,时间超限的缘故原由是每次都要对$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. }
复制代码
到此这篇关于php数据流中第K大元素的盘算方法及代码分析的文章就介绍到这了,更多相关php数据流中第K大元素的盘算方法内容请搜刮草根技术分享以前的文章或继承欣赏下面的相关文章希望各人以后多多支持草根技术分享!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作