Kth Largest Element in Unsorted Array

Given an integer array `nums` and an integer `k`, return the `k`th largest element in the array. Note that it is the `k`th largest element in the sorted order, not the `k`th distinct element. Can you solve it in `O(n)` average time complexity? ### Constraints - `1 <= k <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` ### Input Format - Line 1: An integer `k`. - Line 2: Space-separated integers representing `nums`. ### Output Format Print the `k`th largest element.