PHP怎么计算数据流中的第K大的元素
这篇文章主要讲解了“PHP怎么计算数据流中的第K大的元素”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“PHP怎么计算数据流中的第K大的元素”吧!
创新互联建站从2013年成立,是专业互联网技术服务公司,拥有项目成都做网站、网站制作网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元西林做网站,已为上家服务,为西林各地企业和个人服务,联系电话:18982081108
利用最小堆的性质,该最小堆的根结点一定是所有结点中最小的。所以,我们只需要维护K个元素大小的最小堆。只要是大于最小堆的根结点的值,就移除该根结点的值,把该值插入最小堆中。
设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。
示例:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
说明: 你可以假设 nums 的长度≥ k-1 且k ≥ 1。
理解题意
最开始没理解这道题,读了几遍明白了,k 是指定的位置,然后一组数,按从大到小排列,然后返回第 k 个元素,最基础考虑是每次 add 都需要一次排序,然后重新查找第 k 个元素的值,例如 5,3,6,2 四个数,倒叙之后是6,5,3,2,则 k = 2 的情况下,返回5,然后 add 1的情况,追加在最末尾,不影响结果,add 7 的情况,追加在最开头,返回值变成 6。
解题思路
直接使用最小堆,堆的大小为 k,这样保证空间占用最小,最小堆的根节点是就是最小值,也是我们想要的结果。PHP 的 SPL 标准库是有最小堆这个库,直接在代码中继承 SplMinHeap 。
PHP 实现
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(); $this->insert($val); } return $this->top(); }} /** * Your KthLargest object will be instantiated and called as such: * $obj = KthLargest($k, $nums); * $ret_1 = $obj->add($val); */
感谢各位的阅读,以上就是“PHP怎么计算数据流中的第K大的元素”的内容了,经过本文的学习后,相信大家对PHP怎么计算数据流中的第K大的元素这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
文章名称:PHP怎么计算数据流中的第K大的元素
文章来源:http://pwwzsj.com/article/jgedpj.html