考虑一个2000 x 2000的二维布尔阵列100000个元素设置为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);
在最坏的情况下，我们必须遍历100000个单元格才能找到空闲的单元格。
我们是否可以使用一种数据结构，而不是一个二维数组，使我们能够更快地执行此搜索？
最佳答案
如果数据是常量，并且有许多查询：
您可能需要使用k-d tree，并查找最近的邻居。为每个元素插入(i,j)，以便arr[i][j] = false。标准的k-d树使用欧几里德距离，但我认为可以修改它，改为使用曼哈顿距离。
如果数据用于一个查询：
您至少需要Omega(n*m)ops来读取数据并将其插入到任何数据结构中—这样做毫无意义—建议的解决方案只会优于任何数据结构的构建。