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

LeetCode：https://leetcode.cn/problems/kth-largest-element-in-an-array

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        // 为了能原地排序重定义成var
        var nums = nums

        func partition(_ lo: Int, _ hi: Int) -> Int {
            
            var i = lo, j = hi
            // 使用挖坑填数大法：以第一个元素为基准存入pivot，相当于在nums[i]处先挖个坑
            let pivot = nums[i]

            while i < j {
                // 从右到左找第一个比基准值大的位置
                while i < j, nums[j] <= pivot { j -= 1 }
                // 填入左边坑位，此时nums[j]处形成新的坑位
                nums[i] = nums[j]

                // 从左到右找第一个比基准值小的位置
                while i < j, nums[i] >= pivot { i += 1 }
                // 填入右边坑位，此时nums[i]处形成新的坑位
                nums[j] = nums[i]
            }
            // 最终i==j，把基准值放入最后这个坑位
            // 此时基准值左边元素都大于等于它本身
            nums[i] = pivot
            // 返回基准值位置
            return i
        }

        func fastFind(_ lo: Int, _ hi: Int) -> Int {
            if lo > hi { return -1 }
            // 寻找一个
            let i = partition(lo, hi)
            if i == k - 1 {
                // 第K大等于基准值位置,返回该元素值即可
                return nums[i]
            } else if i < k - 1 {
                // 第K大在基准值位置右侧
                return fastFind(i+1, hi)
            } else/* if i > k - 1 */ {
                // 第K大在基准值位置左侧
                return fastFind(lo, i-1)                
            }
        }

        return fastFind(0, nums.count - 1)
    }
}

image.png