STLset <int> sとがあると仮定すると、その中の要素の数が 未満であるint xとどのように数えることができますか?sx
私はO(log n)（または同様の、より合理的に優れたO(n)）解決策を探しています。
についてはすでに知っていますstd::distance(s.begin(), s.lower_bound(x))が、 s はランダム アクセスではないO(n)ため、それは だと思います。set
8112 次
3 に答える
19
必要なのは「順序統計ツリー」です。rank(x)これは本質的に、 element として以下のキーを持つ要素の数を与える追加の操作をサポートする拡張 (バイナリ検索) ツリーですx。コーメン、ライサーソン、リベスト、スタインの第14章。「アルゴリズム入門」では、アルゴリズムの背景について説明します。
ウェブ上にもいくつかの実装があります。
于 2013-03-10T10:55:03.993 に答える
7
それは不可能だと思います。あなたのSTLセットはツリーベースの構造なので、要素の存在をチェックするだけでもO(log n)です。あなたのツリーのノードは、サブブランチのサイズをどのフィールドにも格納していないため (私が知る限り)、ツリーの構築に使用されるルールに直接従わないプロパティを持つノードをカウントするために必要な操作の数は少なくなりません。これらのノードの数よりも。x より小さい値を持つノードの数が事前にわからないため、最悪のパフォーマンスは、すべてのノードが x より小さい場合です。これは、O(n) の最悪の場合の複雑さを意味します。値 x がツリーにあったとしても、そのノードを見つけるには O(log n) 操作が必要ですが、それらをカウントするためにすべての左側の子孫を訪問する必要があります。したがって、複雑さは一致するノードの数に依存し、最悪の場合は O(n) になります。おそらく、ツリーのノードにデータを追加すれば、それよりもうまくいくでしょう。
于 2013-03-10T10:10:15.033 に答える
6
私のコメントへのフォローアップとして: (セットの代わりに) 赤黒二分探索木を使用して、各ノードがそのノードに根ざしたノードの数を格納する場合 (ノードを挿入/削除するたびに更新されます)、「 X" 統計よりも多い/少ないノードの数は非常に高速です。
于 2013-03-10T10:09:04.440 に答える