【C++】TopK問題!
2750 ワード
例えば、
arr[] = {9,1,6,2,3,8,3,4,7,0}
の最大4つの要素は6,7,8,9
です.アイデア:小さなスタックを使用して、まず配列の中のK個の要素をスタックに挿入して、それからK番目から配列を遍歴して、もし配列の中の要素が大きいならば、スタックの上の要素、トップの要素popに対して、それから配列の中の要素pushをスタックの中に入れます
実装コード:
#include
using namespace std;
#include
class compare{
public:
bool operator()(int a,int b){
return a > b;
}
};
int* FindTopK(int* arr,int n,int* ret,int m){
compare com;
priority_queue<int,vector<int>,greater<int> > q(arr,arr+m);
int i = m;
for(;iif(arr[i] > q.top()){
q.pop();
q.push(arr[i]);
}
}
int j = 0;
while(!q.empty()){
ret[j++] = q.top();
q.pop();
}
}
int main(){
int arr[] = {9,4,5,2,5,1,7,3,1,8};
int ret[5];
FindTopK(arr,10,ret,5);
for(int i = 0;i<5;i++)
cout<" ";
return 0;
}