数组中的第K个最大元素-leetcode - CodeTheWorld

[CodeTheWorld]

https://codetheworld.github.io/2018/11/25/leetcode-215-kth-largest-element-in-an-array.html

[nber1994]

使用quick select方法

func findKthLargest(nums []int, k int) int {
    return quickSelect(nums, 0, len(nums)-1, k)
}

func quickSelect(nums []int, left, right, k int) int {
    if k > 0 && k <= right-left+1 {
        pos := partition(nums, left, right)
        fmt.Println(pos)
        fmt.Println(nums)

        if pos-left == k-1 {
            return nums[pos]
        }
        if pos-left > k-1 {
            return quickSelect(nums, left, pos-1, k)
        }
        return quickSelect(nums, pos+1, right, k-(pos-left+1))
    }
    return -1
}

func partition(nums []int, left, right int) int {
    p := nums[left]
    tmpl, tmpr := left, right
    for {
        for nums[tmpr] < p && tmpl < tmpr {
            tmpr--
        }
        for nums[tmpl] >= p && tmpl < tmpr {
            tmpl++
        }
        if tmpl == tmpr {
            break
        }
        nums[tmpl], nums[tmpr] = nums[tmpr], nums[tmpl]
    }
    nums[tmpl], nums[left] = nums[left], nums[tmpl]
    return tmpl
}