algorithm - 用于在类别的二维网格中搜索坐标的最佳数据结构

Question

我想在二维网格中搜索坐标，其中每个元素存储水平和垂直坐标限制并返回相应的 。

例如:设要查找的坐标为(15,25)，Grid为(其中A、B、C、D、E、F为返回值):

 (0,0) -  (0,10) - (0,20)  - (0,30)
   |   [A]  |  [B]   |  [C]   |
(10,0) - (10,10) - (10,20) - (10,30)
   |   [D]  |  [E]   |  [F]   |
(20,0) - (20,10) - (20,20) - (20,30)
   |   [G]  |  [H]   |  [I]   |
(30,0) - (30,10) - (30,20) - (30,30)

因此，由于我们的坐标 (15,25) 在垂直方向 10-20 和水平方向 20-30 之间，搜索函数应该返回 [F]。

那么在这种情况下，就复杂性而言，哪种数据结构和搜索算法最好？

注意:水平轴和垂直轴的坐标范围已经按升序排列。

Answer 1

暂时忽略您在网格上实际使用的坐标，并沿每个轴将它们标记为 0,1,2,3,...。现在你有了一个漂亮的普通数组。

接下来，找出将实际坐标转换为上一步中定义的伪坐标的函数。在您的示例中，此函数只是整数(或截断)除以 10。当坐标间距不是很好时，您需要小心一点，以确保该函数找到的伪坐标(如你已经画好了)单元格的左上角。

现在您必须进行两次函数调用和一次数组查找。这的复杂性取决于您必须编写的函数的复杂性，以便从坐标转换为伪坐标，但我很难看出这将如何比 O(k) k 的一些小整数值。在数组中查找元素是 O(1)。