algorithm - 找到一对独特的对

Question

给定一组 n 对整数，是否有一种快速的方法来确定集合中是否存在两对 (x_1,y_1) 和 (x_2, y_2) 使得 x_1 != x_2 和 y_1 != y_2？

例如，{(0,1), (0,2), (2,1), (3,2)}有{(0,2), (2,1)}。然而 {(1,0), (2,0), (3,0) 没有任何令人满意的对。

天真的方法只是尝试所有对。其中有 O(n^2) 个。你能得到更接近线性时间的东西吗？

---

如果它加快了速度，我们可以假设这些对按排序顺序存储为数组中的指针(首先是第二个坐标)。

Answer 1

您可以使用以下 O(n) 算法。为了简化符号，我称 (x,y) 为一个点。

请注意，只有当所有点都位于一条平行于轴的直线上时，这样的一对点才存在。通过前两个点确定这条线，然后对于每个新点，检查它是否位于同一条线上。