215.Kth Largest Element in an Array

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 462 | 阅读时间 ≈ 2

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

我的解法

解题思路

可以想把数组排序，然后在返回第k大的数字就可以了

实现代码

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

Runtime: 12 ms, faster than 77.71% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.2 MB, less than 89.39% of C++ online submissions for Kth Largest Element in an Array.

高票解法

C++中排序的时间复杂度为O(NlogN)，如果使用优先队列，对于插入一个大小为k的优先队列插入N次，时间复杂度为O(Nlogk)也可以使用C++中的priority_queue优先队列，默认是大顶堆。

实现代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; i++){
            pq.pop();
        }
        return pq.top();
    }
};

Runtime: 8 ms, faster than 97.45% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.5 MB, less than 40.91% of C++ online submissions for Kth Largest Element in an Array.

代码分析

还可以进一步优化一下，使堆的大小最多保持在k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int num : nums){
            if (pq.size() == k){
                if (num > pq.top()){
                    pq.pop();
                    pq.push(num);
                }
            }
            else
                pq.push(num);
        }
        return pq.top();
    }
};

Runtime: 8 ms, faster than 97.45% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.5 MB, less than 33.33% of C++ online submissions for Kth Largest Element in an Array.

知识总结

学习了C++中priority_queue的使用