題目：

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

示例 1:

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

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說(shuō)明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。

分析：
查找未排序的數(shù)組，找到第k個(gè)最大的元素。
最簡(jiǎn)單的做法應(yīng)該就是對(duì)數(shù)組進(jìn)行排序，然后遍歷拿到第k個(gè)最大元素。那么此時(shí)這道題就是一道排序題了。

但是如果是這樣的話(huà)，這道題就沒(méi)有必要了。應(yīng)該有其他解法，不需要進(jìn)行排序就可以搞定。

因?yàn)橐〉氖堑趉個(gè)，所以感覺(jué)不需要進(jìn)行完全排序即可。
這個(gè)時(shí)候想起來(lái)快速排序?？焖倥判虻奶攸c(diǎn)是先找一個(gè)基準(zhǔn)，讓大于這個(gè)基準(zhǔn)的放在一邊（命名為Array），小于這個(gè)基準(zhǔn)的放在領(lǐng)一邊。

• 如果Array個(gè)數(shù)是k-1，那么這個(gè)基準(zhǔn)就正好是第k個(gè)。
• 如果Array個(gè)數(shù)大于k-1，說(shuō)明第k大元素還是在左邊，繼續(xù)對(duì)左邊進(jìn)行重復(fù)操作
• 如果Array個(gè)數(shù)小于k-1，說(shuō)明第k大元素在右邊數(shù)組里，要對(duì)右邊的數(shù)組進(jìn)行重復(fù)操作。

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個(gè)元素
            return temp
        elif head-left > k-1: # 說(shuō)明第k大元素在左邊
            return self.quickSort(left,head-1,nums,k)
        else: # 說(shuō)明第k大元素在右邊 此時(shí)需要重新計(jì)算k（這個(gè)位置是重點(diǎn)）
            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)