# Two best algorithm to get kth-max number without built-in function

• Algorithm 1:partition (quick sort's) + binary search

``````def findKthLargest(self, nums, k):
target,st,en=-1,0,len(nums)-1
while len(nums)-target!=k:
if target>-1: #binary search
if len(nums)-target>k:st=target+1
else:en=target-1
j,i,target=st-1,st,en
while i<en: #partition
if nums[i]<nums[target]:j+=1;nums[j],nums[i]=nums[i],nums[j]
i+=1
j+=1;nums[j],nums[target]=nums[target],nums[j]
target=j
return nums[target]
``````

Tn=O(nlgn)
Pn=O(1)

Algorithm 2:k-min-priority-heap

``````def findKthLargest(self, nums, k):
self.make_min_heap(nums,k) #create heap
for n in nums[k:]:
if n>nums[0]:n,nums[0]=nums[0],n;self.modify(nums,k,0) #modify top of heap
return nums[0]

def modify(self,nums,k,i):
m=i
if 2*i+1<k and nums[m]>nums[2*i+1]:m=2*i+1
if 2*i+2<k and nums[m]>nums[2*i+2]:m=2*i+2
if m!=i:
nums[m],nums[i]=nums[i],nums[m]
if m<=(k-2)/2:self.modify(nums,k,m)

def make_min_heap(self,nums,k):
for i in range((k-2)/2,-1,-1):self.modify(nums,k,i)
``````

Tn=O(nlgn) but this is more effective than algorithm 1
Pn=O(k)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.