题目描述
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
题目思路
代码 C++
- 思路一、注意不能用 set ，set不允许有重复元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int> temp;
for(int i=0; i < k; i++){
temp.insert(nums[i]);
}
for(int i=k; i < nums.size(); i++){
auto tt = temp.begin();
if(*tt < nums[i]){
temp.erase(tt);
temp.insert(nums[i]);
}
}
auto tt = temp.begin();
return *tt;
}
};
