algorithm - 过滤一些东西的有效方法

Question

有一个 field 列表。每个 field 都有一个给定的价格和一个latlon。用户输入最大距离和最高价格，应用程序返回符合这些条件的场所列表。距离需要在查询中计算，但我可以使用价格或给定的 latlons 制作某种结构。我已经知道如何在 O(n) 中解决这个问题 - 我遍历了一个餐馆列表，如果它们符合条件，就将它们添加到结果中。

有没有办法更有效地做到这一点？我正在考虑使用价格作为 key (可以在运行前计算)制作 BST，然后切掉 BST 中超过价格限制的部分，然后遍历 BST 中的所有内容，但这仍然在O(n)，对吗？

Answer 1

考虑此问题的一种方法是将其视为多维范围搜索问题。每个 field 都可以被认为是三维空间中的一个点，由其经度、纬度和价格给出。如果你想找到给定点的某个半径内的所有 field ，其价格最多是某个数量，那么你正在搜索具有给定中心和半径的圆柱体中的所有点，其上限和下限是最高价格和分别为 0。

您可能需要考虑使用多维搜索树结构(如 k-d 树或 R-树)来解决此问题。获得此结构后，搜索圆柱体边界框的结构以获取候选点列表。然后，测试该框中的每个点，看它是否在圆柱体内。假设这些点分布比较均匀，您会发现其中大约有 π/4 的分数在圆柱体中，因此您不会浪费太多精力。