範囲内で最大および2番目に大きい要素を見つける

StackOverflow https://stackoverflow.com/questions/1412751

質問

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

役に立ちましたか？

解決 

for (e: all elements) {
 if (e > largest) {
   second = largest;
   largest = e;
 } else if (e > second) {
   second = e;
 }
}

largestおよびsecondを適切な下限、またはリストの最初の2つの項目に初期化できます（どちらが大きいかを確認し、リストに少なくとも2つの項目があるかどうかを忘れないでくださいアイテム）

他のヒント

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];

nth_element（begin、begin + n、end、Compare）は、範囲 [begin、の場合、n番目（＆quot; first＆quot;は＆quot; 0th＆quot;）になる要素を配置します。 end）は begin + n の位置でソートされ、 [begin、begin + n）のすべてがソートされたリストのn番目の要素の前に表示されるようにします。必要なコードは次のとおりです。

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

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

リストで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番目に大きい場合はどうなるかを考慮する必要があります。

最適なアルゴリズムは、1.5 * N-2以上の比較を必要としません。 （O（n）であると判断したら、Nの前の係数は何ですか？2 * Nの比較は最適ではありません。）

したがって、最初に「勝者」を決定します。および「敗者」各ペア-0.5 * Nの比較です。

次に、勝者を比較して最大の要素を決定します。これは、さらに0.5 * N-1回の比較です。

次に、最大要素が由来するペアの敗者を他のすべてのペアの勝者と比較することにより、2番目に大きい要素を決定します-別の0.5 * N-1比較。

合計比較= 1.5 N-2。

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

@willの小さな変更が答えます。

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;
   }
}

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

1回のパスでリストをスキャンし、1番目と2番目の値を保存できます。これは、O（n）の効率で、ソートはO（n log n）です。

編集：
部分的なソートはO（n log k）であると思います

テストされていないが楽しい：

template <typename T, int n>
class top_n_functor : public unary_function<T, void>
{

  void operator() (const T& x) {
     auto f = lower_bound(values_.begin(), values_.end(), x);

     if(values_.size() < n) {
         values_.insert(f, x);
         return;
     }

     if(values_.begin() == f)
          return;

     auto removed = values_.begin();
     values_.splice(removed, values_, removed+1, f);

     *removed = x;
  }

  std::list<T> values() {
     return values_;
  }
private:
   std::list<T> values_;
};

int main()
{
  int A[] = {1, 4, 2, 8, 5, 7};
  const int N = sizeof(A) / sizeof(int);

  auto vals = for_each(A, A + N, top_n_functor<int,2>()).values();

  cout << "The top is " << vals.front()
       << " with second place being " << *(vals.begin()+1) << endl;
}

最大の要素が最初の要素の場合、[largest + 1、end）で2番目に大きい要素を検索します。それ以外の場合は、[begin、largest）および[largest + 1、end）で検索し、2つの最大値を取得します。もちろん、これにはO（2n）があるため、最適ではありません。

ランダムアクセスイテレータを使用している場合、クイックソートと同様に、常にエレガントな再帰を使用できます。

template< typename T >
std::pair<T,T> find_two_largest(const std::pair<T,T>& lhs, const std::pair<T,T>& rhs)
{
  // implementation finding the two largest of the four values left as an exercise :) 
}

template< typename RAIter >
std::pair< typename std::iterator_traits<RAIter>::value_type
         , typename std::iterator_traits<RAIter>::value_type > 
find_two_largest(RAIter begin, RAIter end)
{
  const ptr_diff_t diff = end-begin;
  if( diff < 2 )
    return std::make_pair(*begin, *begin);
  if( diff < 3 )
    return std::make_pair(*begin, *begin+1);
  const RAIter middle = begin + (diff)/2;
  typedef std::pair< typename std::iterator_traits<RAIter>::value_type
                   , typename std::iterator_traits<RAIter>::value_type > 
    result_t;
  const result_t left = find_two_largest(begin,middle);
  const result_t right = find_two_largest(middle,end);

  return find_two_largest(left,right);
}

これにはO（n）があり、 NomeNの実装。

通常、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でメモリをalloc / freeにするとキャッシュラインが不要になります。 STLアロケータールールに違反せずに静的状態を提供します。

正確な2の特殊なアルゴリズムほどではありませんが、固定 k＆lt;＆lt; n の場合、デルタが小さい場合（2n + delta * n）を推測します-DEK ACP vol3 S＆amp; Sはまとめられており、デルタの見積もりはもう少しやりたい作業です。

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

bestは2n + k（log k）で、k bestが最初です

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top