画图 / 变量,区间定义 / 伪代码

分区的操作和快排一模一样

这里的伪代码实际找的是第k-1小的数 , 因此在这里做了转换

第k大的数 = 第len-k+1小的数 len=end+1

然后实际是找第k-1索引处的数 , 因此为end+1-k+1-1
(其实这里的定义有点混乱了 , 不管怎样第一次Accepted了 , 之后再改进 )

LeetCode Kth Largest Element in an Array

结果

func partition(nums []int, start int, end int) int {
    p := start
    j := start + 1
    i := start

    v := nums[p]

    for j <= end {
        if nums[j] < v {
            tmp1 := nums[j]
            nums[j] = nums[i+1]
            nums[i+1] = tmp1

            i++
            j++
        } else if nums[j] >= v {
            j++
        }
    }

    tmp2:=nums[i]
    nums[i]=nums[p]
    nums[p]=tmp2

    p=i
    return p
}

func findKthLargest(nums []int, k int) int {

    start:=0
    end:=len(nums)-1

    //实际找的是第k-1小的数 , 因此在这里做了转换
    //第k大的数 = 第len-k+1小的数  len=end+1
    //然后实际是找第k-1索引处的数 , 因此为end+1-k+1-1
    return findKthLargestIn(nums,start,end,end+1-k+1-1)

}

func findKthLargestIn(nums []int, start int, end int, n int) int{
    k:=partition(nums,start,end)

    if k==n {
        return nums[k]
    }
    if k<n {
        return findKthLargestIn(nums,k+1,end,n)
    }
    if k>n {
        return findKthLargestIn(nums,start,k-1,n)
    }
    return 0
}