题解 | #寻找第K大#

基于快排思想选择分割点，在选择递归区间时可以分治讨论，不需要做全局快排。 注意朴素选择left作为哨兵是过不了长用例的，需要使用随机数选择进行优化。

import "math/rand"
import "time"
func findKth( a []int ,  n int ,  K int ) (res int) {
    // write code here
    var quickFind func(left int,right int)
    quickFind = func(left int,right int) {
        //i := rand.Int() % (r - l + 1) + l
        recordP := rand.Int() % (right - left + 1) + left
        a[recordP],a[left] = a[left],a[recordP]
        explodeIndex := left
        for i := left + 1;i <= right;i++ {
            if a[i] >= a[left] {
                explodeIndex++
                a[i],a[explodeIndex] = a[explodeIndex],a[i]
            }
        }
        a[left],a[explodeIndex] = a[explodeIndex],a[left]
        if explodeIndex == (K - 1) {
            res = a[explodeIndex]
            return
        }else if(explodeIndex > (K - 1)) {
            quickFind(left,explodeIndex - 1)
        }else if(explodeIndex < (K - 1)) {
            quickFind(explodeIndex + 1,right)
        }
    }
    rand.Seed(time.Now().UnixNano())
    quickFind(0,n - 1)
    return
}