GO题解 | #寻找第K大#

go解题答案

• 时间复杂度O(n)
• 思路概括：倒序快排
• 思路核心：
  1、因为是第K大，所以倒序快排，
  2、和中间点比较，可以每次只需处理一半的数据

func findKth( a []int ,  n int ,  K int ) int {
    res:=quickSort(a,0,n-1,K)
    return res
}

func quickSort(arr []int,left int,right int,K int)int{
    if left<=right{ // 因为会有重复值，所以要等于
        p:=partition(arr,left,right)
        if p==K-1{ 
            return arr[p] //等于直接输出
        }else if p<K-1{
            return quickSort(arr,p+1,right,K) // 排一半
        }else{
            return quickSort(arr,left,p-1,K) 
        }
    }
    return -1
}
func partition(arr []int,left int,right int)int{
    p:=arr[left]
    for left < right{
         for left < right && arr[right] < p{
            right--
        }

        if left < right {
             arr[left]= arr[right]

             left++
        }
        for left < right && arr[left] > p{
            left++
        }

        if left < right {
            arr[right]= arr[left]

             right--
        }

    }
    arr[left]=p
    return left
}

如果有帮助请点个赞哦， 更多文章请看我的博客

题主背景

• 从业8年——超级内卷500Q技术经理——目前专注go和微服务架构