Related Topics
Data Structure
import heapq
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for i in range(k, len(nums)):
if nums[i] > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, nums[i])
return heap[0]
And here is an implementation for finding the kth smallest element using a max heap:
import heapq
def kth_smallest(nums, k):
heap = [-x for x in nums[:k]]
heapq.heapify(heap)
for i in range(k, len(nums)):
if nums[i] < -heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, -nums[i])
return -heap[0]
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.