Table of Contents
Kth Largest Element in an Array
Logic
- Use minheap to maintain top largest k elements
Golang solution
Kth Largest Element in an Array
type MinHeap []int
func (h MinHeap) Len() int {
return len(h)
}
func (h MinHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h MinHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
//old := *h
length := len(*h)
item := (*h)[length-1]
(*h) = (*h)[0 : length-1]
return item
}
func findKthLargest(nums []int, k int) int {
h := &MinHeap{}
heap.Init(h)
for i := 0; i < len(nums); i++ {
heap.Push(h, nums[i])
if h.Len() > k {
heap.Pop(h)
}
}
return heap.Pop(h).(int)
}Output
Input
nums = [3,2,1,5,6,4]
k = 2
Output
5
Expected
5Largest k elements in array
// find kth largest element
package main
import (
"container/heap"
"fmt"
)
type MinHeap []int
func (h MinHeap) Len() int {
return len(h)
}
func (h MinHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h MinHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
//func (h *MinHeap) Pop() interface{} {
// old := *h
// length := len(old)
// item := old[length-1]
// *h = old[0 : length-1]
// return item
//}
func (h *MinHeap) Pop() interface{} {
//old := *h
length := len(*h)
item := (*h)[length-1]
(*h) = (*h)[0 : length-1]
return item
}
func findKthLargest(nums []int, k int) int {
result := make([]int, k)
h := &MinHeap{}
heap.Init(h)
for i := 0; i < len(nums); i++ {
heap.Push(h, nums[i])
if h.Len() > k {
heap.Pop(h)
}
}
for j := 0; j < k; j++ {
result[j] = heap.Pop(h).(int)
}
return result
}
func main() {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
k := 3
answer := findKLargest(nums, k)
fmt.Printf("answer%#v", answer)
}Output
answer[]int{8, 9, 10}
Program exited.
Please visit https: https://codeandalgo.com for more such contents
Leave a Reply