Python heapq, O(n lg k)

  • 0
    class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        h = []
        for n in nums:
            if len(h) < k:
                heapq.heappush(h, n)
                heapq.heappushpop(h, n)
        return h[0]

  • 0

    Sorry, I didn't get it.

    Does this code return the minimum element?

    I think the heapq maintain the min heap, right?

  • 0

    Yes, it's a min heap. So it always pops its smallest element. So in the end, since it popped all the small elements, it contains the k largest elements. And the smallest of those is the k-th largest element.

Log in to reply

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