给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

    示例 1:
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

    示例 2:
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

    1. // 方法1:快排
    2. func findKthLargest(nums []int, k int) int {
    3.     quickSort(nums,0,len(nums)-1)
    4.     return nums[len(nums)-k]
    5. }
    7. func quickSort(nums []int,left,right int){
    8.     if left > right {
    9.         return
    10.     }
    11.     l,r,privot := left,right,nums[left]
    12.     for l < r {
    13.         for l < r && nums[r] > privot{
    14.             r--
    15.         }
    16.         for l < r && nums[l] <= privot {
    17.             l++
    18.         }
    19.         nums[l],nums[r] = nums[r],nums[l]
    20.     }
    21.     nums[left],nums[l] = nums[l],nums[left]
    22.     quickSort(nums,left,l-1)
    23.     quickSort(nums,l+1,right)
    24. }
    26. // 方法2:快排的优化
    27. func findKthLargest(nums []int, k int) int {
    28.     TopKSplit(nums, len(nums)-k, 0, len(nums)-1)
    29.     return nums[len(nums)-k]
    30. }
    32. func Parition(nums []int, start, stop int)int{
    33.     if start >= stop{
    34.         return -1
    35.     }
    36.     pivot := nums[start]
    37.     l, r := start, stop
    38.     for l < r{
    39.         for l < r && nums[r] >= pivot{
    40.             r--
    41.         }
    42.         nums[l] = nums[r]
    43.         for l < r && nums[l] < pivot{
    44.             l++
    45.         }
    46.         nums[r] = nums[l]
    47.     }
    48.     // 循环结束，l与r相等
    49.     // 确定基准元素pivot在数组中的位置
    50.     nums[l] = pivot
    51.     return l
    52. }
    54. func TopKSplit(nums []int, k, start, stop int){
    55.     if start < stop{
    56.         index := Parition(nums, start, stop)
    57.         if index == k{
    58.             return
    59.         }else if index < k{
    60.             TopKSplit(nums, k, index+1, stop)
    61.         }else{
    62.             TopKSplit(nums, k, start, index-1)
    63.         }
    64.     }
    65. }
    67. 作者：ybzdqhl
    68. 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/topklei-wen-ti-xiang-jie-by-ybzdqhl-w7lo/
    69. 来源：力扣（LeetCode）
    70. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。