[Go] LeetCode 703. Kth Largest Element in a Stream

Description

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your class will have a constructor which accepts an integer and an integer array , which contains initial elements from the stream. For each call to the method , return the element representing the kth largest element in the stream.

Example:

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

Note:
You may assume that ' length ≥ and ≥ 1.

Solution

package _703_kth_largest_element_in_a_stream

/* Heap, PriorityQueue */

import (
"container/heap"
)

// KthLargest object will be instantiated and called as such:
// obj := Constructor(k, nums);
// param_1 := obj.Add(val);
type KthLargest struct {
k int
heap intHeap
}


func Constructor(k int, nums []int) KthLargest {
h := intHeap(nums)
//Convert to heap
heap.Init(&h)

return KthLargest{
k: k,
heap: h,
}
}

func (kl *KthLargest) Add(val int) int {
heap.Push(&kl.heap, val)

//Pop minimum element until len(h) = k and kthlargest = h[0]
for len(kl.heap) > kl.k {
heap.Pop(&kl.heap)
}

return kl.heap[0]
}

type intHeap []int

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{}) {
*h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
res := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return res
}

Site Reliablity Engineer in Tokyo. SRE/devops/Go/AWS/Terraform/Kubernetes/Docker

Site Reliablity Engineer in Tokyo. SRE/devops/Go/AWS/Terraform/Kubernetes/Docker