条件を満たす特定のintのベクトルを効率的に検索する方法はありますか？

Question

私はベクトルを検索する効率的な操作を書こうとしています。具体的には、A1> A2 & & A2 < A3の3つのint（A1、A2、A3）の存在を識別しています。

A {5,3,1,2,3}とすると、出力[3,1,2]、[3,2,3]、[5,1,3]、[5 、1,2]

明らかアプローチ三個のネストされたループを使用することであろう。明らかに、これは非常に非効率的である

int my_function() 
{ 
    std::vector<int> A {3,5,3,1,2,3}; 
    for(auto IT1 = A.begin(); IT != A.end(); IT1++) 
    { 
    for(auto IT2 = IT1 + 1; IT2 != A.end(); IT2++) 
    { 
     for(auto IT3 = IT2 + 1; IT3 != A.end(); IT3++) 
     { 
     if(*IT1 > *IT2 && *IT3 > *IT2) 
     { 
      //Do stuff 
     } 
     } 
    } 
    } 
} 

を、単一ループでこのような動作を行う任意の公知の方法がありますか？または3つのネストされたループより効率的ですか？

Answer 1

このようなトリプレットをすべて見つけたい場合は、そのようなトリプレットの数が最大でO(N^3)になる可能性があるため、漸近的に高速なものはありません。

UP： Hovewer、あなたは何とかそんなに、このようなトリプレットは、（あなたがそれらのT = o(N^3)を持っているとしましょう）そこにいないという保証を持っている場合、あなたはより効率的なアルゴリズムを書くことができます。

配列のすべての要素を反復し、現在の要素をトリプレットの中央に配置してみましょう。これを行うには、現在の値の左側の値と右側の値の2つの順序付けられた値セットを維持する必要があります。ここでは、コードがあります：

// Initialization 
std::multiset<int> left;      // empty set 
std::multiset<int> right(A.begin(), A.end()); // set of all elements in A 
// Iterations 
for (int x : A) { 
    right.erase(x); 
    for (auto l = left.rbegin(); l != left.rend() && *l > x; ++l) { 
     for (auto r = right.rbegin(); r != right.rend() && *r > x; ++r) { 
      // Do stuff with triplet *l, x, *r. 
     } 
    } 
    left.insert(x); 
} 

ようなソリューションの複雑さはTが小さい場合O(N^3)よりもはるかに少ないである、O(T + NlogN)です。欠点は、トリプレットが異なる順序で処理されることです。