私は2つのベクトル/配列上で未定義の交差を実行する効率的なアルゴリズムを書く方法を考え出しましたが、運がありません。私は1つの大きな一意でない配列（一般的には50万から100万の値）と1つの相対的に小さい（おそらく5000値の最大）固有の配列で作業しています。ユニークでないC++のソートされていない交差アルゴリズム
ここでは、unordered_setsなどの手法を使用してさまざまな方法が提案されていますが、いずれかの配列が一意でない場合、これは機能しません。次に、両方の配列に共通の数値を含む出力ベクトルを持つ代わりに、出力ベクトルに大きな配列に対してこれらの共通の値のインデックスが含まれるようにしたいと思います。したがって、大きい方の配列に小さい方の配列の値の1つと等しい5つの位置がある場合は、それらの5つのインデックスのそれぞれが必要です。おそらく、Pythonのin1d関数に似たものでしょう。
誰もが考えている？ありがとう
unordered_setにユニークな側面を置き、非ユニークな面を1つずつ通過します。 unordered_set(unique_side)にあるnon_unique_side[i]の商品を見つけた場合は、iを追加してください。
unordered_setがO(1)償却挿入し、検索時間を設定したハッシュとして実装されると仮定すると、このアルゴリズムはあなたにLが大きく、リスト内の項目数があるO(L+S)時間の複雑さを、取得、およびSは、内のアイテムの数ですより小さいセット。これはあなたが交差点をすることができるほど速いです。
それは私が探していたように聞こえます。ありがとう。 – zach
@zach：この回答を受け入れることを忘れないでください –
大きな配列をその値からintにマップできます。
例えば：あなたは、より大きな配列をマッピングする場合unordered_map<int,int>
は、ちょうどあなたがあなただけの小さな値の上に移動する必要があります
その後見つける各項目の値を増加させ、そして各値のために、かどうかを確認それはマップに存在します。存在する場合は、マップされたintの項目数を結果ベクトルに追加します。
5つの6がある場合、map [6] = 5 ..結果値に6の5つのインスタンスを追加するだけです。
編集：
あなたはインデックスをしたい場合は、int型のベクトルにマッピングし、各値のためにあなたが見つけたインデックスのベクトルを維持することができます。
私のコメントに対する回答から、OPは値そのものではなく、固有でない側のアイテムのインデックスを探しているようです。 – dasblinkenlight
これは問題ではありません。インデックスのベクトルにマップできます。 –
大きな配列のすべてのインデックスを含む別のベクターを作成します。次に、あるレベルの間接を使用する述語を使用して索引をソートし、一意の配列に対して同じ処理を実行するか、または定位置でソートします。次に、1レベルの間接を可能にする比較を使用して通常の順序交差を行い、マッピングベクトルからのインデックスを最終結果に置きます。
非固有の側面については、 '{1,2,2,3} 'と{2,3}の共通点を明確にしてください。 – dasblinkenlight
{1,2,3}は、{2,3} – zach
によって交差された{1,2,2,3}の要素のインデックスになります。彼らは効果的にハッシュすることができますか？ –