設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第K大元素的類（class）。注意是排序后的第K大元素，不是第K個(gè)不同的元素。

你的 KthLargest 類需要一個(gè)同時(shí)接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素。每次調(diào)用 KthLargest.add，返回當(dāng)前數(shù)據(jù)流中第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

這道題我們可以想到使用優(yōu)先隊(duì)列來(lái)做，優(yōu)先隊(duì)列的長(zhǎng)度為K，按照從小到大排序，那么取出第K大的就是取出下標(biāo)為0的值

首先我們構(gòu)造一個(gè)小頂堆的數(shù)據(jù)結(jié)構(gòu)

type KthLargest struct {PriorityQueue []int //優(yōu)先隊(duì)列Size int //小頂堆的容量 } func Constructor(k int, nums []int) KthLargest {var ks KthLargestks.Size = kfor index := 0; index < len(nums); index++ {ks.Add(nums[index])}return ks }func (this *KthLargest) Add(val int) int {if len(this.PriorityQueue) < this.Size {this.PriorityQueue = append(this.PriorityQueue, val)} else if this.PriorityQueue[0] <= val {this.PriorityQueue = this.PriorityQueue[1:]this.PriorityQueue = append(this.PriorityQueue, val)}sort.Ints(this.PriorityQueue)return this.PriorityQueue[0] }

這里是一個(gè)耗時(shí)的做法，因?yàn)檫@里每次添加元素的時(shí)候，我們都會(huì)去排序，把堆內(nèi)元素最小的放在最前

而我們可以通過(guò)實(shí)現(xiàn)golang中的堆的幾個(gè)接口來(lái)自定義我們的堆類型

type intHeap []int//下面幾個(gè)方法是實(shí)現(xiàn)head的接口 func (h intHeap) Len() int {return len(h) }func (h intHeap) Less(i, j int) bool {return h[i] < h[j] }func (h intHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i] } func (h *intHeap) Push(x interface{}) {// Push 使用 *h，是因?yàn)?/span>// Push 增加了 h 的長(zhǎng)度*h = append(*h, x.(int)) }func (h *intHeap) Pop() interface{} {// Pop 使用 *h ，是因?yàn)?/span>// Pop 減短了 h 的長(zhǎng)度res := (*h)[len(*h)-1]*h = (*h)[:len(*h)-1]return res }

實(shí)現(xiàn)了之后，我們就可以非常簡(jiǎn)單和快捷的操作堆了

type KthLargest struct {k intheap intHeap }// Constructor 創(chuàng)建 KthLargest func Constructor(k int, nums []int) KthLargest {h := intHeap(nums)heap.Init(&h)for len(h) > k {heap.Pop(&h)}return KthLargest{k: k,heap: h,} }// Add 負(fù)責(zé)添加元素 func (kl *KthLargest) Add(val int) int {heap.Push(&kl.heap, val)if len(kl.heap) > kl.k {heap.Pop(&kl.heap)}return kl.heap[0] }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TimLiuDream/p/10108454.html

總結(jié)

以上是生活随笔為你收集整理的数据流中的第k大元素的golang实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。