Python minHeap solution


  • 1
    B

    Heap sort, maintain a k length min heap. After iterate every element, pop the min element from the heap.
    Time: O(NlogK); Space: O(K)
    Share my solution in case someone don't know how to use min heap in python very well.

    import heapq
    class Solution(object):
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            queue = []
            for i in xrange(len(nums)):
                heapq.heappush(queue, nums[i])
                if len(queue) > k:
                    heapq.heappop(queue)
            return heapq.heappop(queue)
    

  • 0
    S

    Same idea, only shorter:

    import heapq
    
    class Solution(object):
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            return heapq.nlargest(k, nums)[-1]
    

Log in to reply
 

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