1

秩查找问题：在二维空间中，A=(a1,a2)当且仅当 a1>b1 且 b1>b2 时，我们将说一个点支配一个点 B=(b1,b2)。给定一组 n 个点，点 X 的等级是由 X 支配的点数。设计一个算法来找到每个点的等级。

4

3 回答 3

1

按第一个坐标对点进行排序。然后将它们插入到 order-statistics 树中，按第二个坐标对它们进行排序。

插入时排序统计树中的点的排名正是点的数量，由该点支配。

于 2012-11-06T09:05:43.260 回答
0

小波树数据结构解决了这个问题。我认为它的构建与 Evgeny 和 pogo 所描述的过程基本相同。

于 2013-01-25T04:36:55.623 回答
0

使用稳定排序两次，按第一个属性排序，然后按第二个属性排序。最终排序数组中的位置给出了给定点占主导地位的点数。

于 2012-11-06T09:10:56.390 回答