A short, easy to understand Python implementation using Max Heap


  • 0
    class Solution(object):
        def swap(self, nums, i, j):
            t = nums[i]
            nums[i] = nums[j]
            nums[j] = t
        
        def heapify(self, nums, i, n):
            j = 2*i + 1
            while i != j and j < n:
                if nums[i] >= nums[j]: j = i
                if 2*i+2 < n and nums[2*i+2] > nums[j]: j = 2*i+2
                if i!=j: 
                    self.swap(nums, i, j)
                    i = j
                    j = 2*i + 1
        
        def findKthLargest(self, nums, k):
            n = len(nums)
            
            # Build a max heap
            for i in range(n-1, -1, -1):
                self.heapify(nums, i, n)
            
            # Get k elements out
            for i in range(k-1):
                nums[0] = nums[n-1]
                n -= 1
                
                # Maintain heap structure
                self.heapify(nums, 0, n)
            
            return nums[0]
    

Log in to reply
 

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