You are given an unsorted array of integers nums and a positive integer k.
Design an efficient algorithm to find the k-th largest element in the array. The k-th largest element is the element that would appear in position len(nums) - k if the array were sorted in non-decreasing order.
-
Example:
-
Input:
nums = [3, 2, 1, 5, 6, 4]
,
k = 2
-
Output:
5
(the sorted array is
[1, 2, 3, 4, 5, 6]
, so the 2nd largest is 5)
Assumptions and requirements:
-
1 <= k <= len(nums)
.
-
The array may contain duplicate values.
-
Aim for an algorithm with good
average-case
time complexity (better than fully sorting the array if possible).
Tasks:
-
Describe the algorithm you would use to find the k-th largest element, ideally using an in-place partitioning approach inspired by quicksort.
-
Write the core logic in code (in the language of your choice).
-
Analyze the
average-case time complexity
and
space complexity
of your algorithm, and briefly explain why the average-case complexity holds.