寻找第K大

1. 题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

2. 思路

1. 思路一
   • 先对数组顺序排序，排序后取第n-k个
2. 思路二
   • 基于快排对partition改造
   • 原理是partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置

3. 实现

3.1. 排序

func findKthLargest(nums []int, k int) int {
    if len(nums) < k {
        return 0
    }
    sort.Slice(nums, func(i,j int) bool {
        return nums[i] > nums[j]
    })
    return nums[k-1]

}

3.2. 快排partition

func findKthLargest(nums []int, k int) int {
    return findKth(nums, 0, len(nums)-1, k)
}

func findKth(nums []int, left, right, k int) int {
    if left > right {
        return -1
    }

    p := partition(nums, left, right, k)
    if p == k-1{
        return nums[p]
    }else if p < k-1 {
        return findKth(nums, p+1, right, k)
    }else {
        return findKth(nums, left, p-1, k)
    }
}

func partition(nums []int, left, right, k int) int {
    pivot := nums[left]
    for left < right {
        for left < right && nums[right] <= pivot {
            right--
        }
        nums[left], nums[right] = nums[right],nums[left]
        for left < right && nums[left] >= pivot {
            left++
        }
        nums[left], nums[right] = nums[right],nums[left]
    }
    nums[left] = pivot
    return left
}

4. 参考

• 寻找第K大_牛客题霸_牛客网
• 通过 partition 减治 + 优先队列（Java、C++、Python） - 数组中的第K个最大元素 - 力扣（LeetCode）