[分治]215 Kth Largest Element in a

• 分类：分治

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

代码：

Python3自带方法:

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        return nums[-k]

QuickSelect方法:

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.quickSelect(nums,k,0,len(nums)-1)
    
    def quickSelect(self,ans,k,start,end):
        # 结束条件1
        if (start==end):
            return ans[start]
        
        left=start
        right=end
        mid=(start+end)//2
        p=ans[mid]
        
        while(left<=right):
            while(ans[left]>p):
                left+=1
            while(ans[right]<p):
                right-=1
            if(left<=right):
                temp=ans[left]
                ans[left]=ans[right]
                ans[right]=temp
                left+=1
                right-=1
        
        if (start+k-1)<=right:
            return self.quickSelect(ans,k,start,right)
        if (start+k-1)>=left:
            # 在这里k需要修改（别忘了）
            return self.quickSelect(ans,k-(left-start),left,end)
        
        #结束条件2
        return ans[left-1]

讨论：

1.Python自带的方法beat100%特别吊23333
2.是道使用QuickSelect经典题，QuickSelect使用的是分治的方法做的