algorithm - 从二维平面中的一组点中找到一对大小点

Question

下面是一道面试题，我已经尽力解决了。所需的界限小于 O(n^2)。这是问题所在:

You are given with a set of points S = (x1,y1)....(xn,yn). The points are co-ordinates on the XY plane. A point (xa,ya) is said to be greater than point (xb,yb) if and only if xa > xb and ya > yb. The objective is the find all pairs of points p1 = (xa,ya) and p2 = (xb,yb) from the set S such that p1 > p2.

示例:

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

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

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

Answer 1

我不确定你能做到。

示例:设点为 (1,1)、(2,2) ... (n,n)。

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