数据流中的第k大元素的golang实现
程序员文章站
2022-07-02 18:06:08
设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。 你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第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
这道题我们可以想到使用优先队列来做,优先队列的长度为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] }
上一篇: Linux_vsftpd服务配置