215. Kth Largest Element in an Array

[fockspaces]

use heapq to keep heap only contain two elements, and the top is the answer after iterating

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heapq.heappop(heap)

[fockspaces]

we can also find the kth largest with quick sort every time we find the new pivot index, we only make sure the part in the k largest element is sorted well. once the new_pivot_index become len(nums) - k, we knew the k largest element is the pivot

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        left, right = 0, len(nums) - 1
        while True:
            pivot_idx = (left + right) // 2
            new_pivot_idx = self.partition(nums, left, right, pivot_idx)
            if new_pivot_idx == len(nums) - k:
                return nums[new_pivot_idx]
            if new_pivot_idx > len(nums) - k:
                right = new_pivot_idx - 1
            else:
                left = new_pivot_idx + 1
        return -1

    def partition(self, nums, left, right, pivot_idx):
        pivot = nums[pivot_idx]
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        new_pivot_idx = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
                new_pivot_idx += 1
        nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
        return new_pivot_idx