【C++】TopK問題!

2750 ワード

  • 問題の説明:無秩序な配列の中で最大(最小)の前K個の要素を検索しますか?

  • 例えば、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;
    }