# 215. Kth Largest Element in an Array
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
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
# Solution
Approach 1: Sorting.
Approach 2: Max heap.
Approach 3: Partitioning.
# Code (Python)
Approach 1:
def findKthLargest(self, nums: List[int], k: int) -> int:
# most general solution
# O(NlogN)
nums.sort(reverse=True)
return nums[k-1]
Approach 2:
def findKthLargest(self, nums: List[int], k: int) -> int:
# max heap, good when k is close to len(nums)
# max(O(KlogN), O(N))
neg_nums = [-num for num in nums]
heapq.heapify(neg_nums)
for _ in range(k):
popped = heapq.heappop(neg_nums)
return -popped
Approach 3:
def findKthLargest(self, nums: List[int], k: int) -> int:
# QuickSelect / idea of quicksort
# O(N)
if len(nums) == 1 or k == 1:
return max(nums)
if k == len(nums):
return min(nums)
return self._quick_select(nums, len(nums) - k, 0, len(nums) - 1)
# returns the kth smallest(0 indexed!) of the entire array, guaranteed to be in between indices lo and hi (inclusive)
def _quick_select(self, nums, k, lo, hi):
if lo == hi:
return nums[lo]
pivot = nums[(lo + hi) // 2] # better to be random
left, right = lo, hi
while left <= right: # ensure exhaustion
while left <= right and nums[left] < pivot: # left <= right makes sure they don't go too far
left += 1
while left <= right and nums[right] > pivot:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# ends up with right + 1 or 2 == left when array exhausted
# where [lo, right](inclusive) <= pivot, [left, hi] >= pivot
if k <= right: # k is the absolute array index
return self._quick_select(nums, k, lo, right)
elif k >= left:
return self._quick_select(nums, k, left, hi)
else:
return pivot
# Code (C++)
Approach 1:
// Sorting.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
Approach 2:
// Max heap.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
for (int i = 1; i < k; ++i)
{
pq.pop();
}
return pq.top();
}
};
Approach 3:
// Partitioning.
// Everytime we get an element and get its position in the sorted array.
class Solution {
private:
int tryPartition(vector<int>& nums, int head, int tail) {
int left = head + 1;
int right = tail;
while (left <= right)
{
if (nums[left] <= nums[head])
left++;
else if (nums[right] >= nums[head])
right--;
else
std::swap(nums[left], nums[right]);
}
std::swap(nums[head], nums[right]); // need a swap.
return right;
}
public:
int findKthLargest(vector<int>& nums, int k) {
int head = 0;
int tail = nums.size() - 1;
int headIndex = -1;
int targetIndex = nums.size() - k;
while (head <= tail)
{
headIndex = tryPartition(nums, head, tail);
if (headIndex < targetIndex)
head = headIndex + 1;
else if (headIndex > targetIndex)
tail = headIndex - 1;
else
break;
}
return nums[headIndex];
}
};