7

線上の点がこの線のサブセット内にあるかどうかを判断するための最速の方法を探しています。整数のポイントが与えられ、次のいずれかの「リスト」もあります。

  1. 整数で表されるポイント（3、10、1000など）
  2. 私が2つの整数で表す間隔（2:10は、2から10までのすべての整数、50：60など）

この例では、ポイントの値が5の場合、55の場合と同じように、間隔に含まれているためtrueを返します。ポイントが1000に等しい場合は、ポイントのリストと一致するため、trueも返します。

私は、この状態をチェックするための高速な方法（線形よりも速い）を探しています。可能なポイントの数だけ整数をインスタンス化する必要はありません（つまり、1：1000の間隔では、1000個の整数をインスタンス化する必要はありません）。これは対数時間で実行できますか？

ありがとう

編集：データのリストを前処理するのにかかる時間は0に等しいと見なすことができます。これは、最初の間隔が処理されたら、このテストを10kポイントに適用する必要があるためです。

4

6 に答える 6

11

うーん、多分あなたは間隔またはセグメントツリーを使うことができます：

于 2012-04-12T19:57:40.503 に答える
4

整数の範囲がソートされていて、範囲が重複していない場合は、バイナリ検索を実行して、対数時間で正しい範囲を見つけることができます。

範囲に制約はありますか？それに基づいて、あなたはおそらく一定時間で検索するためのハッシュ関数を思い付くことができます。しかし、これは制約がどのようになっているかによって異なります。

于 2012-04-12T19:54:48.193 に答える
2

反射後、次のコードは、マップの作成に必要な時間を除いて、対数時間で機能するはずだと思います。

enum pointType {
    point,
    open,
    close
};
std::map<long int, pointType> mapPoints;

mapPoints.insert(std::pair<long int, pointType>(3, point));

//create the 5:10 interval:
mapPoints.insert(std::pair<long int, pointType>(5, open));
mapPoints.insert(std::pair<long int, pointType>(10, close));

int number = 4;
bool inside = false;
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number);

if(it1->first == number || it1->second == close) {
    inside = true;
}

マップが重複しない間隔で適切に埋められている限り、これは機能するはずです。

于 2012-04-12T21:18:16.790 に答える
0

まず、ポイントのhash_mapを確認します。それは簡単なチェックです。

次に、最初の座標で区間のマップを並べ替えてから、ポイントのlower_boundを見つけます。

次に、返された要素に含まれているかどうかを確認します。あなたがその中にいなければ、あなたは誰にもいません。

于 2012-04-12T19:53:14.947 に答える
0

ツリーの構築にかかる時間をカウントしない場合は、ツリーデータ構造（Bツリーをお勧めします）が与えられた場合、劣線形時間でそれを行うことができます（ほとんどのツリーの構築にはn log nまたは同様の時間がかかります）。

単純なリストがある場合は、最悪の場合、すべてのポイントと間隔をチェックする必要がある可能性があるため、線形よりも優れた方法はありません。

于 2012-04-12T19:55:37.610 に答える
0

ブルームフィルターを使用してポイントをテストし、線形O（1）時間でそれが間隔内にないかどうかを確認できます。そのテストに合格した場合は、バイナリ検索などの別の方法を使用して、O（log n）時間で確実に間隔の一部であるかどうかを確認する必要があります。

于 2012-04-12T20:06:42.850 に答える