3

以下是我努力解决的一个面试问题。要求的界限是小于O(n^2)。这是问题所在：

你得到一组点 S = (x1,y1)....(xn,yn)。这些点是 XY 平面上的坐标。当且仅当且时，称点 (xa,ya)大于点。目标是从集合 S 中找到所有点对 p1 = (xa,ya) 和 p2 = (xb,yb)，使得 p1 > p2。(xb,yb)xa > xbya > yb

例子：

Input S = (1,2),(2,1),(3,4)

Answer: {(3,4),(1,2)} , {(3,4),(2,1)}

我只能想出一个O(n^2)解决方案，包括与其他点检查每个点。如果有更好的方法，请帮助我。

4

3 回答 3

3

我不确定你能做到。

示例案例：设点为 (1,1), (2,2) ... (n,n)。

有 O(n^2) 个这样的点，输出它们本身需要 O(n^2) 时间。

于 2012-07-26T14:03:38.140 回答
2

我假设你真的想计算这样的对。

x按in降序排序O(n log n)。现在我们将问题简化为一个维度：对于每个位置k，我们需要计算它之前有多少个数字大于 position 处的数字k。这相当于计数倒置，这个问题在这个网站上已经回答了很多次，包括我，例如这里。

解决该问题的最简单方法O(n log n)是使用合并排序算法，如果您想在单击该链接之前自己考虑一下。其他方法包括使用二叉索引树（fenwick 树）或二叉搜索树。实践中最快的可能是使用二叉索引树，因为它们只涉及按位操作。

如果你想打印这些对，你不能比O(n^2)最坏的情况做得更好。不过，我也会对输出敏感O(num_pairs)算法感兴趣。

于 2012-07-26T15:10:24.677 回答
0

为什么不按 X 和 Y 作为二级索引对点列表进行排序？( O(nlogn) )

然后你可以只给出一个“惰性”指示器，显示每个点右侧的所有点都比它大。

如果你想全部找到它们，无论如何都需要O(n^2)，因为有O(n^2)对。

考虑一个排序列表，第一个是最小的，所以有 n-1 个更大的点，第二个有 n-2 个更大的点......加起来大约是 (n^2)/2 == O(n^ 2)

于 2012-07-26T13:20:45.410 回答