7

最大の要素を削除して再度検索せずに上記を見つけるにはどうすればよいですか? これを行うより効率的な方法はありますか？これらの要素が重複しているかどうかは問題ではありません。

4

12 に答える 12

22

partial_sortを使用していますか?

std::partial_sort(aTest.begin(), aTest.begin() + 2, aTest.end(), Functor);

例：

std::vector<int> aTest;

    aTest.push_back(3);
    aTest.push_back(2);
    aTest.push_back(4);
    aTest.push_back(1);


    std::partial_sort(aTest.begin(), aTest.begin()+2,aTest.end(), std::greater<int>());

    int Max = aTest[0];
int SecMax = aTest[1];
于 2009-09-11T19:12:02.760 に答える
7

nth_element(begin, begin+n,end,Compare)[begin, end)範囲が position でソートされた場合に n 番目 (「最初」は「0 番目」)になる要素を配置し、ソートされたリストの n 番目の要素の前にbegin+nすべての要素が表示されるようにします。[begin,begin+n)したがって、必要なコードは次のとおりです。

nth_element(container.begin(),
            container.begin()+1,
            container.end(),
            appropriateCompare);

最大の 2 つだけを探しているので、これはあなたの場合にうまく機能します。あなたの適切な比較が物事を最大から最小に並べ替えると仮定すると、2 番目に大きい要素は位置 1 にあり、最大の要素は位置 0 になります。

于 2009-09-11T19:27:02.213 に答える
2

リスト内の 2 つの最大の一意の値を見つけるつもりであると仮定しましょう。

リストがすでにソートされている場合は、最後から 2 番目の要素を調べます (または、最後から 2 番目の値を探して最後から反復します)。

リストがソートされていない場合は、わざわざソートしないでください。並べ替えはせいぜい O(n lg n) です。単純な線形反復は O(n) であるため、追跡している要素をループするだけです。

v::value_type second_best = 0, best = 0;
for(v::const_iterator i=v.begin(); i!=v.end(); ++i)
   if(*i > best) {
     second_best = best;
     best = *i;
   } else if(*i > second_best) {
     second_best = *i;
   }

もちろん他の基準もあり、これらはすべてループ内のテストに入れることができます。ただし、両方とも同じ最大値を持つ 2 つの要素を見つける必要があるという意味であれば、3 つ以上の要素がすべてこの最大値を持つ場合、または 2 つ以上の要素が 2 番目に大きい場合にどうなるかを考慮する必要があります。

于 2009-09-11T19:13:01.403 に答える
1

答えは、値だけが必要なのか、それとも値を指す反復子が必要なのかによって異なります。

@のマイナーな修正は答えます。

v::value_type second_best = 0, best = 0;
for(v::const_iterator i=v.begin(); i!=v.end(); ++i)
{
   if(*i > best)
   {
     second_best = best;
     best = *i;
   }
   else if (*i > second_best)
   {
     second_best = *i;
   }
}
于 2009-09-11T19:25:58.017 に答える
0

top kは通常、n（log k）よりも少し優れています。

 template <class t,class ordering>
 class TopK {
 public:
    typedef std::multiset<t,ordering,special_allocator> BEST_t;
    BEST_t best;
    const size_t K;
    TopK(const size_t k)
        : K(k){
    } 
    const BEST_t& insert(const t& item){
        if(best.size()<k){
            best.insert(item);
            return best;
        }
        //k items in multiset now
        //and here is why its better - because if the distribution is random then
        //this and comparison above are usually the comparisons that is done; 
        if(compare(*best.begin(),item){//item better than worst
           erase(begin());//the worst
           best.insert(item); //log k-1 average as only k-1 items in best
        } 
        return best;
    } 
    template <class it>
    const BEST_t& insert(it i,const it last){
        for(;i!=last;++i){
            insert(*i);    
        }
        return best;
    }
  };

もちろん、special_allocator本質的には、k個のマルチセットvalue_typesの配列と、それらのノードのリスト（他のkは、新しいものを入れるときまでマルチセットで使用されているため、通常は何もありません）を消去して、 std :: multisetでこれを使用するか、メモリの割り当て/解放を行うと、キャッシュラインのがらくたがyaを殺してしまいます。STLアロケータのルールに違反せずに静的な状態を与えるための（非常に）小さな作業です。

正確に2の特殊なアルゴリズムほど良くはありませんが、固定k<<nの場合、デルタが小さい場合は（2n + delta * n）と推測します-私のDEK ACP vol3 S＆Sは詰め込まれており、デルタの見積もりは私が望むもう少し作業ですやること。

平均最悪は、逆の順序ですべてが異なる場合、n（log（k-1）+ 2）を推測します。

最高は2n+k（log k）であり、kが最初である場合

于 2009-09-25T20:50:02.780 に答える
0

n..m からサブリストを作成し、降順に並べ替えます。次に、最初の 2 つの要素を取得します。元のリストからこれらの要素を削除します。

于 2009-09-11T19:11:26.117 に答える