在二维平面上从一组点中找到大-小点对

Question

以下是一道我努力解决的面试问题。所需限制应小于O(n^2)。以下是问题：

给定一组点S=(x1,y1)....(xn,yn)，这些点是XY平面上的坐标。如果且仅当xa > xb和ya > yb时，点(xa,ya)被认为大于点(xb,yb)。目标是从集合S中找到所有满足p1>p2的点对p1=(xa,ya)和p2=(xb,yb)。

例子：

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

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

我只能提出一个O(n^2)的解决方案，它涉及到对每个点进行检查。如果有更好的方法，请帮我一下。

- uyetch

---

你需要“计算有多少这样的配对”还是“打印所有这样的配对”？ 对于前者，你很可能可以获得比O(n^2)更好的结果，但对于后者则不行。 - IVlad

Answer 1

我不确定你能做到。 示例案例：假设点为(1,1)，(2,2)...(n,n)。

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

- ElKamina

---

+1，但面试官可能更感兴趣的是计算成对数量，而不是打印它们。至少这是一个更有趣的问题。 - IVlad

Answer 2

我假设你是想要计数这样的对。

按照x降序排序，时间复杂度为O(n log n)。现在我们将问题降维到了一维：对于每个位置k，我们需要计算在它之前有多少个数比位于位置k的数字大。这等价于计算逆序对，这个问题在本站上已经被回答过多次，包括我的回答，例如这里。

最简单的方法是使用归并排序算法获得O(n log n)的时间复杂度，如果您想在点击该链接之前自己思考的话。其他方法包括使用二叉索引树（Fenwick Trees）或二叉搜索树。在实践中速度最快的可能是使用二叉索引树，因为它们只涉及位运算。

如果要打印出这些对，最坏情况下无法超越O(n^2)的时间复杂度。然而我会很感兴趣看到一个输出敏感的O(num_pairs)算法。

- IVlad

Answer 3

为什么不按X排序点列表，然后将Y作为次要索引？ (O(nlogn))

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

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

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

- Yochai Timmer

---

是的，但这并没有改善时间复杂度。经过认真思考后，我会选择朴素方法，就像这个方法一样，它的时间复杂度为O(n^2)。 - uyetch

@ard，这种方法可以在不到O(n^2)的时间内准备好所有的配对。如果您不需要实际列出它们，这将为您带来巨大优势。例如，您可以通过此结果执行各种搜索或查询，而无需达到O(n^2)。 - Yochai Timmer