Solution 1

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

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

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

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

Solution 2

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

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

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // sort(nums.begin(), nums.end(), greater<int>());
        // 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 + 2
            largest = pos

            if lson < len(nums) and nums[largest] < nums[lson]:  
                largest = lson
            if rson < len(nums) and nums[largest] < nums[rson]:
                largest = rson

            if 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