同じアイテムを見つけるために 2 つのコンテナーを効率的に検索する方法について質問があります。
たとえば、私は を持っていてtwo list A, B、リスト A のリスト B で一致するすべての項目を把握したいと考えています。
この場合、2 つの loopS が必要で、1 つは別のループ内にあります。Aの各アイテムに対して、Bで全体を検索するため、良くありません。
それを解決するためのアイデアや標準ライブラリ（ブーストはOK）がありますか？
どうもありがとう！
1055 次
5 に答える
4
std::sort()コンテナを使用できますstd::set_intersection()（このアルゴリズムの名前については完全にはわかりません）。複雑さは、シーケンスのサイズではO(n ln n + m ln m)なくO(n * m)、サイズになります。nm
于 2013-11-06T12:27:14.340 に答える
3
2 つのリスト A (サイズ n) と B (サイズ m) がある場合、ネストされたループを使用して、A に存在する B のすべての要素を見つけることは O(nm) です。
hash setを使用することをお勧めします。B の要素を使用してハッシュ セットを作成すると、セットの作成に O(m) を費やし、次に Hash_set(B) で A のすべての要素を検索するのに O(n) を費やすことになります。したがって、複雑さは O(n+m) になります
于 2013-11-06T12:29:54.513 に答える
0
最初に A と B を配列でソートできるかもしれません。次に、同じ要素を数えます。これは O(n*log(n)) ですが、さらにスペースが必要です。
于 2013-11-06T12:29:27.513 に答える