3

例: リストがあります:

1 2 3 7 8 9 11 12

範囲 (A,B) がリストと重複しているかどうかを確認する必要があります。たとえば、範囲 (4, 6) はリストと重複しておらず、範囲 (10, 12) と範囲 (5,9) はリストと重複しています。リストを hashSet に入れることができることはわかっています。次に、範囲内の要素がそのセットに含まれているかどうかを確認します。これには O(N) のコストがかかります。N は範囲の長さです。この問題を解決するためのより良いアルゴリズムはありますか? インターバル ツリーのデータ構造があることは知っていますが、よくわかりません。その構造はlogNでこの問題を解決できますか?

4

5 に答える 5

4

リストがソートされているようです。まだソートされていない場合は、最初にソートします。

重複R = (start, end)しているかどうかを確認するために確認したい範囲を とします。

ソートされたリストのstartとの位置をバイナリ検索できます。end

  • リストに と が連続して表示される場合start、endそれらは重複しません

例えば

1 2 3 4 6 7 8 9 11 12

  • それ以外の場合、それらの間にあるリストの要素があるため、範囲が重複します

見よ:

1 2 3 7 8 9 10 11 12

これはO(log N)で、Nはリスト内の要素の数です。

于 2013-03-22T18:09:55.183 に答える
3

リストがソートされていない場合:

O(M) (M はリスト内のアイテムの数) は、各アイテムをチェックしてリストを反復処理し、低 <= アイテム <= 高かどうかを確認します。

ドメインが「合理的に」制限されている場合の代替:

リストをビット ベクトルとして表します。範囲をビット ベクトルとして表現し (このベクトルのオン ビットは連続します)、ベクトルを「AND」して、共通のビットがあるかどうかを確認します。

于 2013-03-22T18:15:11.603 に答える
1

リストがソートされている場合、範囲内の最小の要素がリストに配置される場所と、範囲内の最大の要素が配置される場所を見つけることができます。これには 2 lg(n) の時間がかかります。これらのインデックスが異なる場合、範囲はリストと交差します。そうでなければ、私は知りません。

于 2013-03-22T18:11:11.967 に答える
1

明らかに、リストがソートされていない場合、範囲クエリ用のアドホック構造を構築するアルゴリズムは O(n) を使用します。リストのソートには O(n log n) かかります。

セット (バランスの取れた二分木として実装) を使用すると、範囲の下限 (または上限) を挿入し、次 (または前) の要素 (データ構造操作をサポートする必要があります。二分木では簡単です)。

範囲クエリの非常に効率的な構造はB+tree です。これにより、O(log b n+k)の範囲を見つけることができます。ここで、b はツリーのランク (つまり、各ノードのサブノードの数) です。これは、範囲内の要素のリストも返すことに注意してください (たとえば、ツリー データセットの 2 つのイテレータとして)。

もう 1 つの興味深い構造は、O(log log n) に要素を挿入するVan Emde Boas木です。上記のセットと同じトリックを使用して、同じ時間計算量で答えを見つけることができます。X ファスト トライと Y ファスト トライも参照してください。

于 2013-03-22T19:00:21.020 に答える
0

配列に A または B があることだけを知りたいことは理解しています。2 つの手順を実行するだけなので、並べ替えを使用する必要はありません。

1- search that is there A or B in your array.(you can do it in O(n))
2- find minimum and maximum.(you can do it in o(n)).

o（n）で完全に実行できますが、o（n）未満では実行できません。このリンクの同じ質問についてこれを調べます。

于 2013-03-23T01:01:10.010 に答える