3

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

在二维平面中找到一个长度大小为 R 且具有给定 n 个点的正方形

条件：

--平行于轴的边，它至少包含n个点中的5个

运行复杂度与 R 无关

他们告诉我给他们 O(n) 算法

4

2 回答 2

4

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

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

输出：(u,v)使得有角的正方形(u,v)至少(u+R, v+R)包含 5 个点P，如果不(u,v)存在，则为 NULL

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

RxR考虑用正方形平铺平面。构造一个稀疏矩阵，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与我们的平铺不对齐。为了测试第二种情况，我们将考虑来自四个相邻图块的点。

迭代中的非空条目B。对于每个非空条目B[i][j]，请考虑条目本身所表示的图块以及上方和右侧的图块中包含的点的集合。这些是条目中的要点：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)目标。

于 2013-03-12T02:35:10.880 回答
1

Run through set once, keeping the 5 largest x values in a (sorted) local array. Maintaining the sorted local array is O(N) (constant time performed N times at most).

Define xMin and xMax as the x-coordinates of the two points with largest and 5th largest x values respectively (ie (a[0] and a[4]).

Sort a[] again on Y value, and set yMin and yMax as above, again in constant time.

Define deltaX = xMax- xMin, and deltaY as yMax - yMin, and R = largest of deltaX and deltaY.

The square of side length R located with upper-right at (xMax,yMax) meets the criteria.

Observation if R is fixed in advance:

  • O(N) complexity means no sort is allowed except on a fixed number of points, as only a Radix sort would meet the criteria and it requires a constraint on the values of xMax-xMin and of yMax-yMin, which was not provided.
  • Perhaps the trick is to start with the point furthest down and left, and move up and right. The lower-left-most point can be determined in a single pass of the input.
  • Moving up and right in steps and counitng points in the square requries sorting the points on X and Y in advance, which to be done in O(N) time requiress that the Radix sort constraint be met.
于 2013-03-11T20:05:49.220 回答