kth_largest_element_in_an_array
1import heapq 2 3 4# @leet start 5class Solution: 6 """ 7 This solution finds the kth largest element of an array by using a heap. 8 This finds the element in $O(k log n)$ time, which is faster than sorting. 9 10 First, we create a copy of the heap, where every item is multiplied by -1. 11 This turns the heap from a min heap into a max heap. 12 Then, for k - 1 times, we pop from the top of the heap, and then return the last popped value, 13 negated. 14 15 This finds the kth largest item. 16 17 The fastest way to do this is in $O(n)$ time, which uses quickselect, along with a median of medians method. 18 It's a little complicated to do, and can be $O(n^2)$ in the worst case without using Median of Medians. 19 """ 20 21 def findKthLargest(self, nums: list[int], k: int) -> int: 22 heap = [-num for num in nums] 23 heapq.heapify(heap) 24 for _ in range(0, k - 1): 25 heapq.heappop(heap) 26 return -heapq.heappop(heap) 27 28 29# @leet end 30sol = Solution() 31 32 33def test(): 34 assert sol.findKthLargest([1, 2, 3], 2) == 2 35 assert sol.findKthLargest([3, 2, 1], 2) == 2
class
Solution:
6class Solution: 7 """ 8 This solution finds the kth largest element of an array by using a heap. 9 This finds the element in $O(k log n)$ time, which is faster than sorting. 10 11 First, we create a copy of the heap, where every item is multiplied by -1. 12 This turns the heap from a min heap into a max heap. 13 Then, for k - 1 times, we pop from the top of the heap, and then return the last popped value, 14 negated. 15 16 This finds the kth largest item. 17 18 The fastest way to do this is in $O(n)$ time, which uses quickselect, along with a median of medians method. 19 It's a little complicated to do, and can be $O(n^2)$ in the worst case without using Median of Medians. 20 """ 21 22 def findKthLargest(self, nums: list[int], k: int) -> int: 23 heap = [-num for num in nums] 24 heapq.heapify(heap) 25 for _ in range(0, k - 1): 26 heapq.heappop(heap) 27 return -heapq.heappop(heap)
This solution finds the kth largest element of an array by using a heap. This finds the element in $O(k log n)$ time, which is faster than sorting.
First, we create a copy of the heap, where every item is multiplied by -1. This turns the heap from a min heap into a max heap. Then, for k - 1 times, we pop from the top of the heap, and then return the last popped value, negated.
This finds the kth largest item.
The fastest way to do this is in $O(n)$ time, which uses quickselect, along with a median of medians method. It's a little complicated to do, and can be $O(n^2)$ in the worst case without using Median of Medians.
sol =
<Solution object>
def
test():