たとえば、Person（名前、名前など）オブジェクトを含む2つのベクトルがあります。ベクトルの1つ（「大」と名付けましょう）を取得し、このベクトルの各要素について、2番目の要素（「小」）で対応する要素を見つけ、「小」ベクトル要素から「大」ベクトルにデータをマージします。エレメント。この操作は、SQL用語での左結合と非常に似ていますが、データのマージが追加されています。最も簡単な方法は2サイクルを作成することですが、これはO（n ^ 2）時間計算量につながります。STLアルゴリズムでもっとうまくやることはできますか？
1157 次
3 に答える
5
小さいベクトルを並べ替えると、大きいベクトルをスキャンしてマージ部分のO（n log n）を取得し、binary_searchを使用して小さいベクトルの要素を見つけることができます。
于 2011-03-04T16:00:27.873 に答える
2
はい！O（nlogn）時間計算量でそれを行うことができます。O（nlogn）時間かかる2番目のベクトルをソートします。最初のベクトルの各要素について、バイナリ検索を使用して2番目の要素の対応する要素を見つけ（STLにはbinary_searchアルゴリズムがあります）、データを最初のベクトルの要素にマージします。最初のベクトルの各要素について、O（logn）時間を費やしています。したがって、このアプローチの実行時間の複雑さはO（nlogn）です。
于 2011-03-04T16:01:03.560 に答える
2
リストが頻繁に変更されない場合は、両方のリストを並べ替えてから、両方のリストをたどるだけで線形時間でマージを実行できます。
mapリストが常に変更されている場合は、またはなどの「小さな」コンテナを並べ替えた方がよいでしょうset。その場合findは、参加したいビッグリストの各アイテムのセットで使用してください。
于 2011-03-04T16:04:50.267 に答える