在一个无序数组中找到第k大的数

这里是用了最小堆保存当前最大的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