215.Kth Largest Element in an Array

Tags: [heap], [max_heap], [priority_queue]

Com: {fb}

Link: https://leetcode.com/problems/kth-largest-element-in-an-array/#/description

Find thekth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution: Heap, Max Heap

import heapq

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return None

        max_heap = []
        for num in nums:
            max_heap.append((-num, num))
        heapq.heapify(max_heap)

        for _ in xrange(k - 1):
            heapq.heappop(max_heap)

        return heapq.heappop(max_heap)[1]

Note:

• Time complexity = O(klgn), n is the number of the elements of the given nums.
• Space complexity = O(n), n is the number of the elements of the given nums. But if the given nums can be modified, we can modify the nums to a max heap, so that the space complexity = O(1).