1

ランク付けの問題: 2 次元空間では、A=(a1,a2)a1>b1 および b1>b2 の場合に限り、ある点が点 B=(b1,b2) を支配していると言えます。n 点のセットが与えられた場合、点 X のランクは、X によって支配される点の数です。すべての点のランクを見つけるアルゴリズムを設計します。

4

3 に答える 3

1

最初の座標でポイントを並べ替えます。次に、それらを順序統計ツリーに挿入します。これにより、2番目の座標で並べ替えられます。

挿入時の注文統計ツリー内のポイントのランクは、正確にはポイントの数であり、このポイントによって支配されます。

于 2012-11-06T09:05:43.260 に答える
0

安定した並べ替えを 2 回使用して、最初の属性で並べ替え、次に 2 番目の属性で並べ替えます。最終的に並べ替えられた配列内の位置は、特定のポイントが支配しているポイントの数を示します。

于 2012-11-06T09:10:56.390 に答える
0

ウェーブレット ツリー データ構造は、この問題を解決します。その構築は、エフゲニーとポゴが説明したプロセスと本質的に同じだと思います。

于 2013-01-25T04:36:55.623 に答える