題目描述：
BAA206089180489CA8DD88F8A831FFD2.jpg
思路1解析：
采用最小堆的方法： 建立一個含有K個元素的最小堆 因為堆得根是K個元素當(dāng)中最小的也就是說堆頂?shù)脑鼐褪沁@個所有元素中第K大小的的元素腾务，即堆中的K-1個元素都比堆頂元素大昙衅。
算法描述：
a. 建立一個最小堆胰柑。初始化時含有K個元素袖肥，最大只能含有K個元素裙犹，維護好現(xiàn)有堆得性質(zhì)
b. 遍歷輸入的數(shù)組撕捍，當(dāng)最小堆得元素個數(shù)小于K的時候加入到最小堆中骑篙，并重新維護堆的最小性質(zhì)
c. 當(dāng)最小堆的元素等于K的時候鸟蟹，遍歷的每個元素和堆根的元素比較如果比之更大則替換之乌妙，并重新維護堆得性質(zhì)
e. 遍歷結(jié)束后堆頂?shù)脑豱ums[0]就是答案
具體代碼
def findKthLargest_heap(self, nums, k):
length=len(nums)
def LEFT(i):
return 2*i
def PARENT(i):
return i//2
def RIGHT(i):
return 2*i+1
def shift_down(A,i,length): # 元素下沉算法
l =LEFT(i)
r =RIGHT(i)
if l<= length and A[l-1]<A[i-1]:
minimum = l
else:
minimum =i
if r<=length and A[r-1]<A[minimum-1] :
minimum = r
if minimum != i :
A[i-1],A[minimum-1] = A[minimum-1],A[i-1]
shift_down(A,minimum,length)
def build_min(A, k ):
for i in range((k//2),0,-1):
shift_down(A,i,k)
# 1\. 首先在原數(shù)組的基礎(chǔ)上構(gòu)建一個長度為K的最小堆
build_min(nums,k)
# 2\. 從k+1開始1
#雙方的股份
for i in range(k+1,len(nums)+1):
if nums[i-1]> nums[0]:
nums[i-1],nums[0]=nums[0],nums[i-1]
build_min(nums,k)
return nums[0]
思路2解析：
快速選擇排序的方法 ：該方法為快速排序QS的部分選擇算法。具體做法為 ：
1 分區(qū)函數(shù)構(gòu)建 建钥， 講數(shù)組分為兩部分藤韵，（隨機或者固定最后一位）選擇一個主元pivot 的元素，將數(shù)組分割成兩部 左半部分小于主元而右半部分大于主元 且返回主元的位置q , 即：
A[0..q-1]<A[q]<A[q+1. ..length(A )]
2.改進的快速排序算法：在原有的快速排序的遞歸算法當(dāng)中加入判斷 熊经，左側(cè)分區(qū)取得的劃分集合的個數(shù)等于K的話則說明則說明A[q]恰好是第i 個大的元素 之前有i-1個比他小 (i 為要找到位置)
- 如果 i==K 則A [q] 就使我們要找到的第K大的元素 泽艘。
- 如果 i<k 則說明第K大元素應(yīng)該在主元素分割的左側(cè)查找
- 若果 i> k 則說明需要在主元的右側(cè)查找 ，且在這個區(qū)間的位置為 i-k的位置
遞歸查找直至找到K的大小元素為止
代碼：
def findKthLargest(self, nums, k):
return self.select(nums,0,len(nums)-1,k)
def swap(self,a,b):
t=a
a=b
b=t
def partition(self,A,p,r):
pivol= A[r]
i=p-1
for j in range(p,r):
if A[j]<=pivol:
i += 1
if i!=j:
A[j], A[i] =A[i],A[j]
A[r],A[i+1]=A[i+1],A[r]
return i+1
def random_partition(self,A,p,r):
ran=int(p+ (r-p)*random.random())
A[r],A[ran]=A[ran],A[r]
return self.partition(A,p,r)
def select(self,A,p,r,i):
if p==r:
return A[p]
q= self.random_partition(A,p,r)
k= q-p+1
if k ==i :
return A[q]
elif i<k :
return self.select(A,p,q-1,i)
else:
return self.select(A,q+1,r,i-k)
