数组中第K个最大元素

[wisecsj]

https://leetcode-cn.com/problemset/all/?topicSlugs=heap

func findKthLargest(nums []int, k int) int {
    createHeap(nums[:k],k)
    for i:=k;i<len(nums);i++ {
        if nums[i]>nums[0] {
            insert(nums,nums[i],k)
        }
    }
    return nums[0]
    
}
func insert(nums []int,num int,k int) {
    nums[0] = num
    var child int
    for i:=0;2*i+1<k;i=child {
        child = 2*i+1
        if child+1<k && nums[child+1] <nums[child] {
            child++
        }
        if nums[i] >nums[child] {
            nums[i],nums[child] = nums[child],nums[i]
        }else {
            break
        }
    }
}
func createHeap(nums []int,k int) {
    var minChild int
    for i:=(k-2)/2;i>=0;i-- {
        for j:=i;2*j+1<k;j=minChild {
            minChild = 2*j+1
            if minChild+1<k && nums[minChild+1]<nums[minChild] {
                minChild++
            }
            if nums[j] > nums[minChild] {
                nums[j],nums[minChild] = nums[minChild],nums[j]
                
            } else {
                break
            }
        }
    }
}

[wisecsj]

1.先建立一个size为k的最小堆，时间复杂度O（k）
2.然后从从下标为k开始，遍历nums中的元素，与堆顶进行比较，然后调整堆。时间复杂度 O((n-k)logk)