algorithm - 在 2D 平面中找到边长为 R 的正方形？

Question

我在高频交易公司面试，他们问我

在二维平面上给定n个点，找到一个长度为R的正方形

条件:

--轴的平行边并且至少包含n个点中的5个

运行复杂度与R无关

他们让我给他们O(n)算法

Answer 1

有趣的问题，感谢发布!这是我的解决方案。感觉有点不雅，但我认为它符合问题定义:

输入:R，P = {(x_0, y_0), (x_1, y_1), ..., (x_N-1, y_N-1)}

输出:(u,v) 这样带有角的正方形(u,v) 和(u+R, v+R) 包含来自 P 的至少 5 个点，如果不存在这样的 (u,v) 则为 NULL

约束:渐近运行时间应该是O(n)

考虑用 RxR 方 block 平铺平面。构造一个稀疏矩阵，B定义为

B[i][j] = {(x,y) in P | floor(x/R) = i and floor(y/R) = j}

在构造 B 时，如果找到包含至少五个元素的条目，则停止并输出 (u,v) = (i*R, j*R) 为包含五个点的矩阵条目的 i,j。

如果 B 的构造没有产生解决方案，那么要么没有解决方案，要么边长为 R 的正方形与我们的平铺不对齐。为了测试第二种情况，我们将考虑来自四个相邻图 block 的点。

迭代B 中的非空条目。对于每个非空条目 B[i][j]，考虑包含在由条目本身表示的图 block 中以及上方和右侧的图 block 中的点的集合。这些是条目中的点:B[i][j]、B[i+1][j]、B[i][j+1]、B[i+1][j+1]。这个集合中不能有超过 16 个点，因为每个条目必须少于 5 个。检查这个集合并测试这个集合中的点中是否有 5 个点满足问题标准；如果是这样停止并输出解决方案。 (我可以更详细地说明这个算法，但由于 (a) 这样的算法显然存在，并且 (b) 它的渐近运行时间是 O(1)，所以我不会详细介绍) .

如果在 B 中迭代条目后没有找到解决方案，则输出 NULL。

B 的构造只涉及一次遍历 P，因此是 O(N)。 B 不超过 N 个元素，所以迭代它是 O(N)。 B 中每个元素的算法考虑不超过 16 个点，因此不依赖于 N 并且是 O(1)，因此整体解决方案满足 O(N) 目标。