这里是用了最小堆保存当前最大的k个数,堆顶即为top k中最小的数,每次和堆顶的数比较即可,实现直接用了stl的multiset(堆得具体实现这里不在赘述),调整堆得复杂度是logk,需要遍历整个数组,所以总的time cost是o(nlogk)
- 一、使用multiset实现
#include <iostream>
int find_nth_largest(const vector<int> v, int k)
{
int res = 0;
multiset<int> s;
for (int i = 0; i < k; ++i)
{
s.insert(v[i]);
}
for (int j = k; j < v.size(); ++j)
{
s.insert(v[j]);
s.erase(s.begin());
}
return *s.begin();
}
int main() {
vector<int> v4{1, 2, 3, 3, 6, 9};
cout << find_nth_largest(v4, 2) << endl;
vector<int> v5{1, 2, 3, 3, 6, 9, 100, 88, 76};
cout << find_nth_largest(v5, 3) << endl;
}
执行结果
6
76
- 二、使用make_heap实现
#include <iostream>
#include <algorithm>
int find_nth_largest2(vector<int>& v, int n)
{
int res = 0;
while(n-- >0)
{
make_heap(v.begin(), v.end());
pop_heap(v.begin(), v.end());
res = v.back();
v.pop_back();
}
return res;
}
int main() {
vector<int> v4{1, 2, 3, 3, 6, 9};
cout << find_nth_largest2(v4, 2) << endl;
vector<int> v5{1, 2, 3, 3, 6, 9, 100, 88, 76};
cout << find_nth_largest2(v5, 3) << endl;
}
执行结果
6
76
网友评论