实现查找一个无序数组中第k大的元素

给定一个数组和k值，实现查找一个无序数组中第k个大的元素。
取值范围在[0,1000]

方法1: 哈希桶

import collections
class Solution:
    
    def findKthNum(self,nums,k):
        
    
        
        dic = collections.defaultdict(int)
        
        # 取值区间
        Max = 1000
        
        n = len(nums)
        
        for i in range(n):
            dic[nums[i]]+=1
        
        index = 0
        flag = True
        for j in range(0,Max):
            
            if dic[j]!=0:
                
                index+=dic[j]
                
                print("当前位置存放的元素",j,"一共重复了",dic[j],"次")
                
                if index>=k and flag:
                    flag=False
                    print("第",k,"位数为",j)

        
    

a = Solution()
a.findKthNum([0, 3, 1, 12,12,12,12, 34, 2, 6, 21, 78, 9,9,9,9],10)

输入
[0, 3, 1, 12, 12, 12, 12, 34, 2, 6, 21, 78, 9, 9, 9, 9]
输出

当前位置存放的元素 0 一共重复了 1 次
当前位置存放的元素 1 一共重复了 1 次
当前位置存放的元素 2 一共重复了 1 次
当前位置存放的元素 3 一共重复了 1 次
当前位置存放的元素 6 一共重复了 1 次
当前位置存放的元素 9 一共重复了 4 次
当前位置存放的元素 12 一共重复了 4 次
第 10 位数为 12
当前位置存放的元素 21 一共重复了 1 次
当前位置存放的元素 34 一共重复了 1 次
当前位置存放的元素 78 一共重复了 1 次

时间复杂度O(n)
空间复杂度O(d)

方法2:快拍提前终止

class Solution:
    def searchKthNum(self,nums,k):
        n = len(nums)
        self.quickSort(nums,0,n-1,k-1)
        return nums[k-1]
    
    def quickSort(self,nums,start,end,k):
        
        if start>=end:
        
            return 
        
        mid = nums[start]
        l,r = start,end
        
        while l<r:
            
            while l<r and nums[r]>=mid:
                r-=1
            
            nums[l],nums[r] = nums[r],nums[l]
            
            while l<r and nums[l]<mid:
                l+=1
            
            nums[l],nums[r] = nums[r],nums[l]
        
        nums[l] = mid
       
        if l==k:
            return 

        if l>k:
            self.quickSort(nums,start,l-1,k)
        else:
            self.quickSort(nums,l+1,end,k)
       
       

b = Solution()
b.searchKthNum([0, 3, 1, 12,12,12,12, 34, 2, 6, 21, 78, 9,9,9,9],10)

输出
12

时间复杂度：
O(n)，如上文所述，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」。
空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为