考虑一个2000x2000的二维布尔数组。其中有10万个元素为true,其余元素为false。
给定一个单元格(x1,y1),我们需要找到最近的false单元格(x2,y2)(按曼哈顿距离:abs(x1-x2)+abs(y1-y2))。
一种方法是:
给定一个单元格(x1,y1),我们需要找到最近的false单元格(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个单元格。
除了使用2D数组,还有什么数据结构可以让我们更快地执行此搜索吗?