我有一组二维点,我希望能够使用参数 x_min
和 n
进行以下查询:什么是 n
具有最大 y
且具有 x > x_min
的点?
在 Ruby 中改写:
class PointsThing
def initialize(points)
@points = points
end
def query(x_min, n)
@points.select { |point| point.x > x_min }.sort_by { |point| point.y }.take(n)
end
end
理想情况下,我的类也支持插入和删除操作。
我想不出一个数据结构可以使查询在不到 O(|@points|) 的时间内运行。有人知道吗?
最佳答案
按 x 降序对点进行排序。对于每个点,将其插入到 purely functional 中按 y 降序排列的红黑树。将所有中间树保存在一个数组中。
要查找特定的 x_min,请使用二分查找找到中间树,其中恰好插入了 x > x_min 的点。遍历这棵树找到前 n 个点。
预处理成本在时间和空间上为 O(p log p),其中 p 是点数。查询时间为 O(log p + n),其中 n 是查询中要返回的点数。
关于algorithm - 支持对一组二维点进行特定查询的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31153033/