84 lines
1.3 KiB
Markdown
84 lines
1.3 KiB
Markdown
|
---
|
||
|
|
layout: page
|
||
|
|
title: Kth Largest Element in an Array
|
||
|
|
last_solved:
|
||
|
|
category: heap
|
||
|
|
leetcode_url: https://leetcode.com/problems/kth-largest-element-in-an-array/
|
||
|
|
status: Attempted
|
||
|
|
---
|
||
|
|
|
||
|
|
Problem
|
||
|
|
-------
|
||
|
|
|
||
|
|
```
|
||
|
|
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
|
||
|
|
|
||
|
|
Example 1:
|
||
|
|
|
||
|
|
Input: [3,2,1,5,6,4] and k = 2
|
||
|
|
Output: 5
|
||
|
|
Example 2:
|
||
|
|
|
||
|
|
Input: [3,2,3,1,2,4,5,5,6] and k = 4
|
||
|
|
Output: 4
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
Solution
|
||
|
|
----------
|
||
|
|
|
||
|
|
- If you're trying to find the largest kth element, use a min heap.
|
||
|
|
- As you're adding elements, evict elements if length is greater than k
|
||
|
|
- The result is the kth largest element sitting at the root
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
def findKthLargest(self, nums: List[int], k: int) -> int:
|
||
|
|
|
||
|
|
min_heap = []
|
||
|
|
|
||
|
|
for n in nums:
|
||
|
|
|
||
|
|
heapq.heappush(min_heap, n)
|
||
|
|
|
||
|
|
print(min_heap) # added element n
|
||
|
|
|
||
|
|
# if len>5, pop the smallest element (make room for a LARGER one)
|
||
|
|
if len(min_heap)>k:
|
||
|
|
heapq.heappop(min_heap)
|
||
|
|
|
||
|
|
print(min_heap)
|
||
|
|
print()
|
||
|
|
|
||
|
|
return heapq.heappop(min_heap) # can also do `return min_heap[0]`
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
Your input
|
||
|
|
[3,2,1,5,6,4]
|
||
|
|
k=2
|
||
|
|
|
||
|
|
stdout
|
||
|
|
[3]
|
||
|
|
[3]
|
||
|
|
|
||
|
|
[2, 3]
|
||
|
|
[2, 3]
|
||
|
|
|
||
|
|
[1, 3, 2]
|
||
|
|
[2, 3]
|
||
|
|
|
||
|
|
[2, 3, 5]
|
||
|
|
[3, 5]
|
||
|
|
|
||
|
|
[3, 5, 6]
|
||
|
|
[5, 6]
|
||
|
|
|
||
|
|
[4, 6, 5]
|
||
|
|
[5, 6]
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
![image1]()
|