次の表があります。
ブロック | ブロック | 開始 | 終わり
1 | 1 | 4
2 | 5 | 9
3 | 10 | 20
4 | 21 | 50
..........
n | 1000 | 2000年
変数 ci に値が与えられると、c を含むブロックを検索する必要があります ( start < c < end )。たとえば、c = 1001 の場合、c はブロック n にあります。どのデータ構造が最も効率的でしょうか?
5 に答える
1
整数の範囲全体が だけの1..2000場合、データを次のようなテーブルと考えることができます。
n block
1 1
2 1
3 1
4 0
5 0
6 2
.
.
.
2000 要素のベクトルとして実装します。nベクトル内の要素を単純に検索すると、どのブロックnが含まれているかがわかります (0 ベースのインデックスを持つ言語で実装することを選択した場合を除きます。この場合、要素nはどのブロック整数n+1が含まれているかを示します)。ここでは、「ブロックなし」を示すために 0 を使用しました。
ここでの他のいくつかの回答と比較して、これは時間とスペースを交換しますが、それは多くの場合、許容できるトレードオフです。
于 2012-07-05T15:31:14.680 に答える
1
インターバルツリーまたはセグメントツリーが機能します。基本的に、間隔をバイナリ検索して、問題のポイントを含むものを見つけることができます。セグメント ツリーはクエリを刺すのに優れているので、最初に試してみます。
Java を使用している場合は、以前に Java で両方を実装しました。インターバル ツリーはここに、セグメント ツリーはここにあります。
于 2012-07-05T15:46:59.047 に答える
1
この問題にはインターバル ツリーがかなり適していると思います。確かに、テーブルよりも実装がはるかに難しく、ブロックを動的に追加する必要がない場合は、テーブルを維持し、単純なバイナリ検索を使用してブロックを見つけることをお勧めします。これは、ひどいコーディングの苦労をしなくても (間隔を追加する必要がない限り)、間隔ツリーと同じ効率を達成するはずです。
于 2012-07-05T15:47:59.063 に答える
0
何を求めているのかわからない
このようなブロックを実装するには多くの方法があると思います。個人的には、各ブロックの末尾を含む注文リストを作成し、末尾が値よりも大きくなるまでそれを実行します。インデックスはブロックの数を示します
于 2012-07-05T14:59:08.110 に答える
0
この特定の例では、start を配列 (ソート順) に格納し、バイナリ検索を実行して適切なブロックに到達できます。
例を説明する編集：
開始配列には 1,5,10,21,1000 があるため、c=3 の場合、5 はブロック 2 の開始インデックスであるため、ブロック 1 にあることがわかります。
何らかの理由で end も見たい場合は、それを別の配列に格納し、バイナリ検索から取得したインデックスから start の end にアクセスできます。
于 2012-07-05T15:00:19.623 に答える