703.md

topk

解法一 堆

type KthLargest struct {
	k int
	hea *heapInt
}


func Constructor(k int, nums []int) KthLargest {
	var kt KthLargest
	kt.k = k
	var h heapInt
	h = nums
	kt.hea = &h
	heap.Init(kt.hea)
	if len(nums) < k {
		return kt
	}else {
		for kt.hea.Len() > k {
			heap.Pop(kt.hea)
		}
	}
	return kt
}


func (this *KthLargest) Add(val int) int {
	value := 0
	if this.hea.Len() < this.k{
		heap.Push(this.hea,val)
		value = heap.Pop(this.hea).(int)
		heap.Push(this.hea,value)
	}else {
		v := heap.Pop(this.hea).(int)
		if v <= val{
			heap.Push(this.hea,val)
			value = heap.Pop(this.hea).(int)
			heap.Push(this.hea,value)
		}else {
			heap.Push(this.hea,v)
			value = v
		}
	}
	return value
}

type heapInt []int
func(h heapInt)Len()int{
	return len(h)
}
func(h heapInt)Less(i,j int)bool {
	return h[i]<h[j]
}
func(h heapInt)Swap(i,j int){
	h[i],h[j] = h[j],h[i]
}
func(h *heapInt)Push(x interface{}){
	*h = append(*h,x.(int))
}
func(h *heapInt)Pop()interface{}{
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
/**
 * Your KthLargest object will be instantiated and called as such:
 * obj := Constructor(k, nums);
 * param_1 := obj.Add(val);
 */

benchmark:

var (
	s = []int{1,4,543,234,5433,2345,532,523,67,765,34,534,23,5423,56,8,9,76,4,23,4,56,6,7,7,6,5,34,23,5,5,43,5,5,4,5,34,5,5654,34,4,3,765,34,65,654,76,3,876,43,3456,76523,6534,6534,6534,64346,6455,6,7,88,654,234,35,4554,76543}
)


func BenchmarkKthLargest_Add(b *testing.B) {
	c := Constructor(9,s)
	for i := 0; i < b.N; i++ {
		c.Add(43243534)
	}
}

output :

goos: darwin
goarch: amd64
pkg: github.com/googege/test
BenchmarkKthLargest_Add
BenchmarkKthLargest_Add-4   	 4985630	       238 ns/op
PAS