数组中第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

思路

送分题

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]

这样写比我使用希尔排序或者快速排序时间都少，这个是什么操作？

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def backtrac(nums):
            if not nums or len(nums)==1:
                return nums
            left=[x for x in nums if x<nums[0]]
            mid=[x for x in nums if x==nums[0]]
            right=[x for x in nums if x>nums[0]]
            return backtrac(left)+mid+backtrac(right)
        return backtrac(nums)[-k]

上面是使用sort函数，下面是使用快速排序。