原题链接

leetcode上的题目描述:

给定整数数组nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

go语言解法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

func findKthLargest(nums []int, k int) int {
    heap := NewHeap()
    for _, num := range nums {
        heap.Insert(num)
    }
    // fmt.Println(heap)
    re := -1
    for k > 0 {
        re = heap.Pop()
        k--
    }
    return re
}

// 简单实现一个堆
func NewHeap() *Heap {
    heap := &Heap{
        datas: make([]int, 0),
        size: 0,
    }
    return heap
}

type Heap struct {
    datas []int
    size  int
}

func (h *Heap) String() string {
    return fmt.Sprintf("Heap{datas: %v}", h.datas)
}

func (h *Heap) Insert(v int) {
    h.datas = append(h.datas, v)
    h.moveUp(h.size)
    h.size += 1
}

func (h *Heap) Pop() int {
    h.size -= 1
    v := h.datas[0]
    h.datas[0] = h.datas[h.size]
    h.moveDown(0)
    return v
}

func (h *Heap) moveUp(index int) {
    parentIndex := (index - 1) / 2
    for h.datas[index] > h.datas[parentIndex] {
        h.datas[parentIndex], h.datas[index] = h.datas[index], h.datas[parentIndex]
        index = parentIndex
        parentIndex = (index - 1) / 2
    } 
}

func (h *Heap) moveDown(index int) {
    maxIndex := index
    for index * 2 + 1 < h.size {
        if h.datas[index * 2 + 1] > h.datas[index] {
            maxIndex = index * 2 + 1
        }
        if index * 2 + 2 < h.size && h.datas[index * 2 + 2] > h.datas[maxIndex] {
            maxIndex = index * 2 + 2
        }
        if maxIndex == index {
            break
        }
        h.datas[maxIndex], h.datas[index] = h.datas[index], h.datas[maxIndex]
        index = maxIndex
    }
}