Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "what is the calculation method of the K largest element in php data flow". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope that this article "what is the calculation method of the K largest element in php data flow" can help you solve the problem.

Design a class (class) that finds the K largest element in the data stream. Note that it is the sorted K largest element, not the K different element.

Calculation method.

1. Directly use the minimum heap, the size of the heap is k, so as to ensure that the space occupation is minimum, and the root node of the smallest heap is the minimum, which is also the result we want.

2. Php's spl standard library has a minimum heap, which inherits SplMinHeap directly in the code.

Instance class KthLargest extends SplMinHeap {/ * * @ param Integer $k * @ param Integer [] $nums * / static $nums; public $k; function _ _ construct ($k, $nums) {$this- > k = $k; / / iterate through the initialization array and insert foreach ($nums as $v) {$this- > add ($v) into the heap, respectively } * @ param Integer $val * @ return Integer function add ($val) {/ / keeps the heap size k, and inserts data when the heap is not full. If ($this- > count ()

K) {$this- > insert ($val);} elseif ($this- > top ()

Extract (); return $this- > top ();}} * Your KthLargest object will be instantiated and called as such: * $obj = KthLargest ($k, $nums); * $ret_1 = $obj- > add ($val)

Instance expansion:

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];}}

The first idea is that the reason for exceeding the time limit is to reorder the array $this- > nums every time, and it is a waste of time to rearrange the array that has been sorted last time. So, the following solution is to save only the first k elements sorted last time. The number of sorting this time has been reduced. Time has also been reduced.

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];}} this is the end of the content about "what is the calculation method of the Kth element in the php data stream". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.