Kth Largest Element in an Array

LeetCode 215

Heap

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        """
        heapq.heappush(heap, item = (priority, object))
        heapq.heappop(heap)
        heapq.heappushpop(heap, item)
        heapq.nlargest(n, iterable, key=None)
        heapq.nsmallest(n, iterable, key=None)
        """
        heapq.heapify(nums)
        elements = heapq.nlargest(k, nums)
        return elements[-1]

Merge Sort

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        """
        Merge Sort
        """
    
        def divide(nums):
            if len(nums) == 1:
                return nums
            mid = int(len(nums)/2)
            left, right = divide(nums[:mid]), divide(nums[mid:])
            return conquer(left, right)
        def conquer(left, right):
            res = []
            pointer1 = pointer2 = 0
            while pointer1 < len(left) and pointer2 < len(right):
                if left[pointer1] < right[pointer2]:
                    res.append(left[pointer1])
                    pointer1 +=1
                else:
                    res.append(right[pointer2])
                    pointer2 +=1           
            res.extend(left[pointer1:])
            res.extend(right[pointer2:])           
            return res            
        ordered = divide(nums)
        return ordered[-k]