TopK

求第K大数

已知一轮快排可以将一个数组分为两个部分，且两个部分有大小关系，利用这个关系来求解，每一轮快排都能缩小问题的范围，

go快速排序

go快速排序，非递归

CODE

func findKthLargest(nums []int, k int) int {
    var l, r = 0, len(nums) - 1
    return partition(nums, l, r, k)
}

func partition(arr []int,l int, r int, k int) int {
    if l == r {
        return arr[l]
    }

    var i, j int = l-1, r+1
    var mid int = (l + r) / 2
    var x int = arr[mid]
    for i < j {
        i++
        for arr[i] > x {
            i++
        }

        j--
        for arr[j] < x {
            j--
        }

        if i < j {
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // l, j and j+1, r
    var s1 int = j-l+1
    if k <= s1 {
        return partition(arr, l, j, k)
    }
    return partition(arr, j+1, r, k-s1)
}