Solution 1

本题有时间限制，也就是需要在线性时间内完成至少部分排序和查找工作。

第一个思路：不稳定的快速排序。提交了确实能过……

• 时间复杂度： O(N)O(N)O(N)，其中NNN为输入数组的长度，排序的最佳实现可以达到线性复杂度，但是实际并不稳定。
• 空间复杂度： O(log⁡N)O(\log N)O(logN)，其中NNN为输入数组的长度，快速排序过程中的函数递归调用之占用

class Solution {
public:int findKthLargest(vector& nums, int k) {sort(nums.begin(), nums.end(), greater());int ans = nums[k - 1];return ans;}
};

Solution 2

第二个思路：堆排序（优先队列），在线性时间完成构建，对数时间内完成更新，因此我们可以快速建立一个堆，然后将堆顶元素删除k-1次，也可以在近似线性时间内得到结构。

为了方便确定最大值，因此使用大根堆。这次直接使用了C++内建的 make_heap 实现。

• 时间复杂度： O(N)O(N)O(N)，其中NNN为输入数组的长度，本质上的时间复杂度是 O(N+klog⁡N)O(N + k \log N)O(N+klogN)，但是本题的k取值似乎比较理想，因此优化到了忽略后项（能过就很迷）
• 空间复杂度：O(log⁡N)O(\log N)O(logN)，其中NNN为输入数组的长度，建堆和更新时最大的函数低谷调用之占用

class Solution {
public:int findKthLargest(vector& nums, int k) {// sort(nums.begin(), nums.end(), greater());// int ans = nums[k - 1];make_heap(nums.begin(), nums.end());for (int i = 0; i < k - 1; i++) {pop_heap(nums.begin(), nums.end() - i);}int ans = nums[0];return ans;}
};

Solution 3

Solution 1的Python实现

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:nums = sorted(nums, reverse=True)ans = nums[k - 1]return ans

Solution 4

Solution 2的Python实现，本着想使用内建的heapify实现，但是只能处理小根堆

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# nums = sorted(nums, reverse=True)# ans = nums[k - 1]def max_heapify(nums, pos):lson, rson = pos * 2 + 1, pos * 2 + 2largest = posif lson < len(nums) and nums[largest] < nums[lson]:  largest = lsonif rson < len(nums) and nums[largest] < nums[rson]:largest = rsonif largest != pos:nums[largest], nums[pos] = nums[pos], nums[largest]max_heapify(nums, largest)def build_heap(nums):for pos in range(len(nums) // 2 - 1, -1, -1):max_heapify(nums, pos)build_heap(nums)for _ in range(k-1):nums[0], nums[-1] = nums[-1], nums[0]nums.pop() # 直接删除元素max_heapify(nums, 0)ans = nums[0]return ans