题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

样例

算法1：快速排序(从大到小)

时间复杂度：O(n*logn)

C++ 代码

class Solution {
public:

    void quick_sort(vector<int>& nums, int l, int r)
    {
        if(l == r) return;
        int x = nums[(l + r) >>1];
        int i=l-1, j=r+1;
        while(i < j)
        {
            do i++; while(nums[i] > x);
            do j--; while(nums[j] < x);
            if(i < j) swap(nums[i], nums[j]);
        }
        quick_sort(nums, l, j);
        quick_sort(nums, j+1, r);
    }
    int findKthLargest(vector<int>& nums, int k) {
        quick_sort(nums, 0, nums.size()-1);
        return nums[k-1];
    }
};

算法2： 堆排序(小根堆)

时间复杂度：O(n2logn)

C++ 代码

class Solution {
public:
    //实现2： 堆排序,为O(n*2*logn)
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap; //小根堆
        for(int i=0; i<nums.size(); i++) //时间为O(n)
        {
            heap.push(nums[i]); //插入的时间为 O(logn)
            if(heap.size() > k) heap.pop(); //删除的时间为 O(logn)
        }

        return heap.top(); //求最小值的时间 O(1)
    }
};