0

プロジェクトのいくつかの部分を開発するために、データセットのような構造を実装する必要がありました。これにより、最小値と最大値のキー値に応じてサブセットを取得できるようになります。

ConstainedSet <- Set((key,value)*)
Subset <- ConstainedSet.Match(Constraint = "val1 <= key < val2")

次に、サブセットには、「val1 <= key < val2」制限に一致するConstainedSetの要素のみを含める必要があります。つまり、キーがval1以上でval2より小さい要素です。

たとえば、次のようなサブセットがあるとします。

ConstrainedSet <- {(1,hand),(2,eye),(3,nose)}

次に、次のような操作：

Subset <- ConstainedSet.Match(Constraint = "1 <= key < 3")

結果として、次のサブセットが生成されます。

Subset <- {(1,hand),(2,eye)}

各要素が次のようなトリプレットのベクトルに格納されるソリューションを開発しました

(minKey,maxKey+1,value)

このベクトルをminKeyとmaxKeyでソートし、 minKeyの順序をmaxKeyの順序よりも優先します。次に、"Match" を呼び出すたびに、このベクトルに対してバイナリ検索が実行されます。

私が間違っていなければ、最悪の場合の時間の複雑さは次のとおりです。

  • 「Match」への呼び出しごとに O(N)。
  • 挿入の場合は O(N)。

ここで、N はセット内の要素の数です。

より良い解決策はありますか？

4

1 に答える 1

2

キーによってバランスのとれた二分木に格納します。

検索、挿入: O(log n)。

結果をコピーする必要がある場合、それは常に O(n) になりますが、コピーが必要ない場合、サブセットは「反復子」のペアで表すことができ、ツリーから最小ノードと最大ノードのペアを返すことができます、したがって、全体は O(log n) になります。

于 2013-09-24T16:08:33.503 に答える