3

考虑一个 2000 x 2000 2D 布尔数组。100,000 个元素设置为 true，其余为 false。

给定一个单元格 (x1,y1)，我们需要找到最近的错误单元格 (x2,y2)（按曼哈顿距离：abs(x1-x2) + abs(y1-y2)）。

一种方法是：

for (int dist = 0; true; dist++)
    for ((x2,y2) in all cells dist away from (x1,y1))
        if (!array[x2,y2])
            return (x2,y2);

在最坏的情况下，我们必须遍历 100,000 个单元格才能找到空闲的单元格。

有没有我们可以使用的数据结构而不是二维数组来让我们更快地执行这个搜索？

4

2 回答 2

4

如果数据是恒定的并且您有很多查询：
您可能想要使用kd 树，并寻找最近的邻居。插入(i,j)每个元素，使得arr[i][j] = false. 标准 kd 树使用欧几里得距离，但我认为可以修改它以使用曼哈顿距离。

如果数据用于一个查询：
您至少需要Omega(n*m)操作来读取数据并将其插入到任何数据结构中 - 所以这样做没有意义 - 建议的解决方案只会胜过任何数据结构的构建。

于 2012-06-26T08:39:35.517 回答
2

您可能有兴趣查看Region QuadTree。这里最初将整个图像建模为根，因为图像包含全 0（假设）。然后在设置特定像素时，首先将图像分为 4 个象限，将不包括该像素的 3 个象限留作叶子。剩余的象限再次细分，以此类推。直到我们有 4 个点叶子，其中一个被设置。这种表示将有助于在搜索期间排除整个区域，并且搜索时间可以优化到 O(log n)

于 2012-06-26T13:04:48.020 回答