设计一个找到数据流中第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
这道题我们可以想到使用优先队列来做，优先队列的长度为k，按照从小到大排序，那么取出第k大的就是取出下标为0的值
首先我们构造一个小顶堆的数据结构
我要评论type kthlargest struct {
priorityqueue []int //优先队列
size int //小顶堆的容量
}
func constructor(k int, nums []int) kthlargest {
var ks kthlargest
ks.size = k
for 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]
}
这里是一个耗时的做法，因为这里每次添加元素的时候，我们都会去排序，把堆内元素最小的放在最前
而我们可以通过实现golang中的堆的几个接口来自定义我们的堆类型
type intheap []int
//下面几个方法是实现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，是因为
// push 增加了 h 的长度
*h = append(*h, x.(int))
}
func (h *intheap) pop() interface{} {
// pop 使用 *h ，是因为
// pop 减短了 h 的长度
res := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return res
}
实现了之后，我们就可以非常简单和快捷的操作堆了
type kthlargest struct {
k int
heap intheap
}
// constructor 创建 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 负责添加元素
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]
}
如对本文有疑问， 点击进行留言回复！！
VSCode1.4 搭建Golang的开发调试环境(遇到很多问题)
网友评论