题目描述：
BAA206089180489CA8DD88F8A831FFD2.jpg
思路1解析：
采用最小堆的方法： 建立一个含有K个元素的最小堆 因为堆得根是K个元素当中最小的也就是说堆顶的元素就是这个所有元素中第K大小的的元素，即堆中的K-1个元素都比堆顶元素大。
算法描述：
a. 建立一个最小堆。初始化时含有K个元素，最大只能含有K个元素，维护好现有堆得性质
b. 遍历输入的数组，当最小堆得元素个数小于K的时候加入到最小堆中，并重新维护堆的最小性质
c. 当最小堆的元素等于K的时候，遍历的每个元素和堆根的元素比较如果比之更大则替换之，并重新维护堆得性质
e. 遍历结束后堆顶的元素nums[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\. 首先在原数组的基础上构建一个长度为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 分区函数构建 ， 讲数组分为两部分，（随机或者固定最后一位）选择一个主元pivot 的元素，将数组分割成两部 左半部分小于主元而右半部分大于主元 且返回主元的位置q , 即：
A[0..q-1]<A[q]<A[q+1. ..length(A )]
2.改进的快速排序算法：在原有的快速排序的递归算法当中加入判断 ，左侧分区取得的划分集合的个数等于K的话则说明则说明A[q]恰好是第i 个大的元素 之前有i-1个比他小 (i 为要找到位置)
- 如果 i==K 则A [q] 就使我们要找到的第K大的元素 。
- 如果 i<k 则说明第K大元素应该在主元素分割的左侧查找
- 若果 i> k 则说明需要在主元的右侧查找 ，且在这个区间的位置为 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)
