算法 - 数组中的第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
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

分析：
查找未排序的数组，找到第k个最大的元素。
最简单的做法应该就是对数组进行排序，然后遍历拿到第k个最大元素。那么此时这道题就是一道排序题了。

但是如果是这样的话，这道题就没有必要了。应该有其他解法，不需要进行排序就可以搞定。

因为要取的是第k个，所以感觉不需要进行完全排序即可。
这个时候想起来快速排序。快速排序的特点是先找一个基准，让大于这个基准的放在一边（命名为Array），小于这个基准的放在领一边。

• 如果Array个数是k-1，那么这个基准就正好是第k个。
• 如果Array个数大于k-1，说明第k大元素还是在左边，继续对左边进行重复操作
• 如果Array个数小于k-1，说明第k大元素在右边数组里，要对右边的数组进行重复操作。

class Solution:
    def quickSort(self,left,right,nums,k) :
        head,trail,temp = left,right,nums[left]
        if head >= trail:
            return nums[trail]
        #大的放在左边，小的放在右边
        while head < trail:
            while head < trail and nums[trail] <= temp:
                trail -= 1
            nums[head] = nums[trail]
            while head < trail and nums[head] >= temp:
                head +=1
            nums[trail] = nums[head]
        nums[head] = temp
        if head-left == k-1: # 判断是否head就是第k个元素
            return temp
        elif head-left > k-1: # 说明第k大元素在左边
            return self.quickSort(left,head-1,nums,k)
        else: # 说明第k大元素在右边 此时需要重新计算k（这个位置是重点）
            return self.quickSort(head+1,right,nums,k-head-1+left)
        
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSort(0,len(nums)-1,nums,k)