在2D平面上找到方形边长是R？

我是在高频交易公司的采访，他们问我在2D平面上找到方形边长是R？

找到一个正方形，其长度尺寸为R与给定的n个点在2D平面

条件：

--parallel双方轴和它所包含的n个点

运行的复杂性是不是相对于R 1至少5

他们告诉我给他们为O（n）algorit hm

来源

2013-03-11 user2149873

那么你是如何回应的？ – agentp 2013-03-11 20:04:05

R是提前给你的，还是你被允许选择它？ – jerry 2013-03-11 20:28:28

这里必须更加缺少。提出的问题（假设给出R）可能没有解决方案。 – agentp 2013-03-11 21:07:30

通过设置一次，保持（排序的）本地数组中的5个最大的x值。维护排序后的本地数组是O（N）（恒定时间最多执行N次）。

Y上再次定义XMIN和XMAX作为两个点与最大和第五最大的x值分别（即（A [0]和[4]）。

排序一个[]的x坐标值，并且在恒定时间设定YMIN与YMAX如上，再次

定义DELTAX = xMax- XMIN，和移动deltaY作为YMAX - yMin和R =最大DELTAX和移动deltaY的

侧的平方。位于右上方（xMax，yMax）处的长度R符合标准。

观察如果R是固定的预先：

O（N）的复杂性意味着任何排序允许除了在固定数量的点，因为只有一个基数排序将符合标准和它需要的值的约束没有提供xMax-xMin和yMax-yMin。
也许诀窍在于从最下方离开的点开始，向上向右移动。最左下角的点可以在输入的单个路径中确定。
向上和向右移动，在正方形请求中的步骤和计数点上预先排序X和Y上的点，这要在O（N）时间内完成，要求满足基数排序约束条件。

来源

2013-03-11 20:05:49

这不起作用。计数器例子：点是{（100,0），（99,1），（99,2），（101,1），（101,2），（0,100），（1,99），（2 ，99），（1101），（2101）}'。然后，ax [0] = ay [0] = 101'，'ax [4] = ay [4] = 99'，'deltaX = 2'和'deltaY = 2'。但是，轴线对齐的边长为2的方格的右上角位于'（101,101）'处，不包含任何给定的点。另外，我认为OP的问题意味着R是提前提供的常数。我会要求澄清。 – jerry 2013-03-11 20:21:50

你可以定义R吗？我会假设这是一个固定的输入，否则你可以很容易地把它做得足够大来覆盖所有的东西。 – 2013-03-11 20:25:39

@jerry：不要重新选择y的点，使用最大的x的原始5点，然后在y上使用这5个点。你的例子给出了deltaX = 101-2 = 99，deltaY = 101，R = 101. – 2013-03-11 20:27:40

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

输入：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，或NULL如果至少5个点没有这样的(u,v)存在

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

考虑与平铺平面正方形。构造一个稀疏矩阵，B定义为

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

当你正在构建B，如果你发现至少包含五个要素停止含五点矩阵条目i,j的进入和输出(u,v) = (i*R, j*R)。

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

遍历B中的非空条目。对于每个非空条目B[i][j]，请考虑条目自身所代表的瓦片中包含的点以及上方和右侧的瓦片中的点的集合。这些是条目中的点：B[i][j], B[i+1][j], B[i][j+1], B[i+1][j+1]。由于每个条目的数量必须少于5个，因此此集合中的分数不得超过16个。检查此集合并测试此集合中的点数是否满足问题标准的5个点数;如果这样停止并输出解决方案。（我可以更详细地指定这个算法，但是因为（a）这样的算法明显存在，并且（b）其渐近运行时间是O(1)，所以我不会详细讨论）。

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

B的构建只涉及P，因此是O(N)。 B不超过N元素，因此重复它是O(N)。 B中每个元素的算法考虑不超过16个点，因此不依赖于N，因此该总体解决方案符合O(N)目标。

来源

2013-03-12 02:35:10 PaulF

+1 - 你不能跳过空的b [i] [j] - 尽管一个解决方案可能会在空箱子里留下一个左下角。 – agentp 2013-03-12 12:20:09

@george - 很好的接收！我们可以包含来自B [i-1] [j]，B [i-1] [j + 1]的额外的贴图来解决这个问题，并且仍然保持我们想要的渐近性能。 – PaulF 2013-03-12 14:25:46

+1昨天晚上我有类似的想法，但你必须小心'B'以确保复杂度既O（n）又独立于'R'。 'B'可能必须是一个矩形阵列，以便分配和检查相邻瓦片的访问可以在恒定时间内发生。使用初始传递来查找边界，数组将具有“ceil（（maxX-minX）/ R）* ceil（（maxY-minY）/ R）'元素。为了避免检查每个点是否为空，请保留一个未排序的列表，列出n个点中每个点放入哪个图块并对其进行迭代。 – jerry 2013-03-12 15:06:09

在2D平面上找到方形边长是R？

回答

相关问题