Binary Heap solution
from heapq import heappop, heappush
class Solution:
# time O(NlgK) space O(K) K = heap size
def findKthLargest(self, nums: List[int], k: int) -> int:
hp = []
res = 0
n = len(nums)
target = n-k+1
for num in nums:
heappush(hp,-num)
if len(hp) > target:
heappop(hp)
res = heappop(hp)
return -res
Quick selection Sort solution time O(N) on average, worst O(N^1), space O(1) main idea: use partition to seperate array into less than pivot and bigger than pivot, then based on k and partition, adjust the partition range until get the point where partition pivot == nums[len-k]
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# step1: choose a random pivot
piv = random.choice(nums)
# step2 reorder the array as [arr > pivot] + [arr== pivot ] = [arr < pivot]
lo,mi,hi = [l for l in nums if l > piv],[m for m in nums if m == piv],[h for h in nums if h < piv]
#step3: get new reordered arr, left pointer, right pointer, where it means
"""
< p ==p > p
| -------| --------| -----------|
lo hi
hence, if lo<=k, kth largets fails in arr[:left]; if k > hi, kth largets fails in [hi:] subarray, we just need to find k-hi th biggest number; lo<k<=hi, return nums[lo] (since 0-based index )
"""
nums = lo+ mi + hi
# set left, right boundry
left = len(lo)
right = len(lo)+len(mi)
if k <= left:
return self.findKthLargest(nums[:left],k)
elif k > right:
return self.findKthLargest(nums[right:],k-right)
else:
return nums[left]