leetcode:数组中的第K个最大元素

215. 数组中的第K个最大元素

难度中等1787

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

---

这道题有多种解法

思路一：

先将这个数组进行排序，然后返回第k大的元素下标即可。

//第一种写法
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

//第二种写法
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        return nums[k - 1];
    }
};

//第三种写法
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

思路二：

运用优先级队列，将数组的元素放到优先级队列中排序，默认为大堆，然后进行 k - 1次的 pop 掉队头的位置，最后第 k 个大的数字就在对头的位置了！

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //将数组里面的数据先放到优先级队列中，默认为大堆
        priority_queue<int> p(nums.begin(), nums.end());

        //将队列中前k-1个最大的元素pop掉
        for(int i = 0; i < k - 1; ++i)
        {
            p.pop();
        }

        return p.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(K + K*logN)

时间复杂度：O(N)

所以当这个数组很大的时候，可能会导致内存不够，所以可以看下面这种最优的解放。

思路三（最优解法）：

与思路二不同，这次我们用优先级队列存储 k 个数，而且是按小堆存放！

然后让数组里面剩余元素依次与对头比较，若比对头还大的话，则入堆，反之则跳过，依次循环，直到数组遍历完成。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //创建k个空间的小堆
        priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin() + k);
        //将每次大于堆顶的数据入堆
        for(size_t i = k; i < nums.size(); ++i)
        {
            if(nums[i] > p.top())
            {
                p.pop();
                p.push(nums[i]);
            }
        }
        return p.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这种解法当K很大的时候的时间复杂度与思路二差不多：*O(K + (N - K)logK)

但是对于空间复杂度的优化则非常的大：O(K)