欢迎访问LeetCode题解合集

题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解：

法一：

小根堆。

维护一个大小为 k 的小根堆，不停的将 nums 中的元素插入，当堆中元素大于 k 时，删除堆顶元素，最后的堆顶就是第 k 大结果。

时间复杂度：$O(nlogk)$

额外空间复杂度：$O(k)$

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q;
        for ( auto &it : nums ) {
            q.push( it );
            if ( q.size() > k )
                q.pop();
        }
        return q.top();
    }
};
/*
时间：8ms，击败：91.73%
内存：9.9MB，击败：40.03%
*/

法二：

快排。

根据快排思想，判断 pivot 在划分后的位置，假设对于区间 [l, r] 在划分后，左右指针分别为 i 和 j ，pivot 的位置是 i ：

• 如果 i + 1 == k ，返回 pivot
• 如果 i + 1 > k ，需要在左边查找
• 如果 i + 1 < k ，需要在右边查找

时间复杂度：$O(n)$

额外空间复杂度：$O(logn)$

class Solution {
public:
    int quick_sort( int l, int r, vector<int>& nums, int k ) {
        if ( l == r ) return nums[l];
        int i = l, j = r;
        int rand_idx = rand() % ( r - l + 1) + l;
        swap( nums[l], nums[rand_idx] );
        int pivot = nums[l];
        while ( i < j ) {
            while ( i < j && nums[j] <= pivot ) --j;
            if ( i < j ) nums[i++] = nums[j];
            while ( i < j && nums[i] >= pivot ) ++i;
            if ( i < j ) nums[j--] = nums[i];
        }
        nums[i] = pivot;
        if ( i + 1 == k ) return pivot;
        else if ( i >= k ) return quick_sort( l, i - 1, nums, k );
        else return quick_sort( i + 1, r, nums, k );
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort( 0, nums.size() - 1, nums, k );
    }
};
/*
时间：4ms，击败：99.20%
内存：9.8MB，击败：49.24%
*/

下面贴一个选择左边界为 pivot 的情况：

class Solution {
public:
    int quick_sort( int l, int r, vector<int>& nums, int k ) {
        if ( l == r ) return nums[l];
        int i = l, j = r, pivot = nums[l];
        while ( i < j ) {
            while ( i < j && nums[j] <= pivot ) --j;
            if ( i < j ) nums[i++] = nums[j];
            while ( i < j && nums[i] >= pivot ) ++i;
            if ( i < j ) nums[j--] = nums[i];
        }
        if ( i + 1 == k ) return pivot;
        else if ( i >= k ) return quick_sort( l, i - 1, nums, k );
        else return quick_sort( i + 1, r, nums, k );
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort( 0, nums.size() - 1, nums, k );
    }
};
/*
时间：44ms，击败：33.27%
内存：9.7MB，击败：83.19%
*/

在贴一个选择中间值为 pivot ：

class Solution {
public:
    int quick_sort( int l, int r, vector<int>& nums, int k ) {
        if ( l == r ) return nums[l];
        int i = l, j = r;
        int m = (l + r) >> 1;
        swap( nums[l], nums[m]);
        int pivot = nums[l];
        while ( i < j ) {
            while ( i < j && nums[j] <= pivot ) --j;
            if ( i < j ) nums[i++] = nums[j];
            while ( i < j && nums[i] >= pivot ) ++i;
            if ( i < j ) nums[j--] = nums[i];
        }
        if ( i + 1 == k ) return pivot;
        else if ( i >= k ) return quick_sort( l, i - 1, nums, k );
        else return quick_sort( i + 1, r, nums, k );
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort( 0, nums.size() - 1, nums, k );
    }
};
/*
时间：8ms，击败：91.73%
内存：9.7MB，击败：74.82%
*/

最好不要选择左边界为 pivot 。。。。