Optimized Python minHeap solution with complexity O( n log(min(k,n-k)) ), 55ms


  • 0

    Trick is: when k is larger than half of the length of nums, simply do the reverse problem of find the (n-k+1)-th largest element of a negated nums, below is my solution

    from heapq import *
    class Solution(object):
        def findKthLargest(self, nums, k):
            if k > len(nums)/2+1:
                return -self.findKthLargest([-num for num in nums], len(nums)-k+1)
            heap = []
            for num in nums:
                if len(heap) < k:
                    heappush(heap, num)
                else:
                    if num >= heap[0]:
                        heappop(heap)
                        heappush(heap, num)
            return heap[0]

Log in to reply
 

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