LeetCode 215 Kth Largest Element in an Array

LeetCode 215 Kth Largest Element in an Array Problem

Download Code
class Solution(object):
    # def findKthLargest(self, nums, k):
    #     """
    #     :type nums: List[int]
    #     :type k: int
    #     :rtype: int
    #     """
    #     return sorted(nums, reverse=True)[k - 1]

    # def findKthLargest(self, nums, k):
    #     # build min heap
    #     heapq.heapify(nums)
    #     # remove n - k smallest number
    #     while len(nums) > k:
    #         heapq.heappop(nums)
    #     return nums[0]
    #     #return heapq.nlargest(k, nums)[-1]

    def findKthLargest(self, nums, k):
        # shuffle nums to avoid n*n
        return self.quickSelection(nums, 0, len(nums) - 1, len(nums) - k)

    def quickSelection(self, nums, start, end, k):
        if start > end:
            return float('inf')
        pivot = nums[end]
        left = start
        for i in range(start, end):
            if nums[i] <= pivot:
                # swip left and i
                nums[left], nums[i] = nums[i], nums[left]
                left += 1
        nums[left], nums[end] = nums[end], nums[left]
        if left == k:
            return nums[left]
        elif left < k:
            return self.quickSelection(nums, left + 1, end, k)
            return self.quickSelection(nums, start, left - 1, k)
Download Kth Largest Element in an Array.py

List of all Kth Largest Element in an Array problems

Leetcode 215 Kth Largest Element in an Array problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.