給定一個數(shù)組和k值烤送，實現(xiàn)查找一個無序數(shù)組中第k個大的元素糠悯。
取值范圍在[0,1000]

方法1: 哈希桶

import collections
class Solution:
    
    def findKthNum(self,nums,k):
        
    
        
        dic = collections.defaultdict(int)
        
        # 取值區(qū)間
        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,"位數(shù)為",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 位數(shù)為 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)阅悍，遞歸使用棧空間的空間代價的期望為