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大的数(这里可以Note里备注的k永远合法)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
return nums[nums.size() - k];
}
};
让人惊讶的是试水解法居然击败80%的提交:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
return nums[nums.size() - k];
}
};
另一种方法是使用stl的heap:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
make_heap(nums.begin(),nums.end());
for(int i = 0;i < k - 1;i++)
{
pop_heap (nums.begin(),nums.end());
nums.pop_back();
}
return nums.front();
}
};
运行结果:
Runtime: 24 ms, faster than 61.26% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.2 MB, less than 57.31% of C++ online submissions for Kth Largest Element in an Array.
内置函数nth_element:
Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//这里使用k-1原因是如果last等于end,算法无效
nth_element(nums.begin(), nums.begin() + k - 1 , nums.end(), greater<int>());
return nums[k - 1];
}
};
执行结果击败100%
Runtime: 4 ms, faster than 100.00% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.1 MB, less than 78.18% of C++ online submissions for Kth Largest Element in an Array.
另一个内置函数可以解决这个问题:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
return nums[k - 1];
}
};