寻找一对独特的配对（在IT技术中）

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)种情况。你能否得到更接近线性时间的算法？

如果加快速度，我们可以假设这些整数对按照第一个坐标，然后是第二个坐标的顺序存储为一个数组中的指针。

- marshall

---

你最好添加你已经完成的内容。 - herohuyongtao

@herohuyongtao 你可以尝试所有可能的配对，但这需要O(n^2)的时间。我想知道是否有更接近线性时间的方法。 - marshall

你可以使用哈希表实现的集合)来获得O(n)。 - loopbackbee

@goncalopp 你要往集合里放什么？你不能把所有的成对的元素都放进去。 - marshall

@marshall 把每一对放进集合里就可以了。你是说你不能把所有的对都放进去吗？另外，重新读一下你的问题，它并没有多少意义。如果集合的大小>1，则给定n对整数的集合中存在两个不同的对... 你是指“组”还是“列表”？ - loopbackbee

@goncalopp（修正了注释中的拼写错误。）我们正在寻找“整数对的整数对”，而不是整数对。考虑{(2,0)，(3,0)，(4,0)}。在这个集合中没有一对满足我的标准的整数对。 - marshall

Answer 1

你可以使用以下的O(n)算法。为了简化表示，让我称(x,y)为一个“点”。

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

- Łukasz Kidziński

---

你是指与x轴或y轴平行的直线吗？毕竟(1,1)，(2,2)，(3,3)形成一条直线。 - marshall

我喜欢我们的答案：数学家会抓狂！ - Ziggy

Answer 2

如果前两对是 (x1, y1) 和 (x1, y2) [y1 != y2]，那么在剩余的配对列表中，如果你发现任何一个 x != x1，则其相应的 y 不应该等于 y1 或者不等于 y2。

- Abhishek Bansal

---

是的，那听起来是正确的。所以实际上它是线性时间。然而，我在想，如果你假设这些配对已经按排序顺序放置在数组中，它甚至可能是常数时间。你能否只查看第一个和最后一个配对？ - marshall

Answer 3

第二次尝试：

你需要：1个图形和1个整数i。

在迭代过程中将您的配对放入一个有向图中，使得对于每个(x, y)都有一个有向边x -> y。添加边到图后，检查两个顶点：

如果x和y顶点都具有零度，则增加i。 否则，对于每个度数为2的顶点，递减i。

只要i > 0，就存在一对满足条件的配对。

- Ziggy

---

我猜这里的“度”是一个二元组 (a, b)，其中 a 是入射边的数量，b 是离开顶点的边的数量（相对于入射而言，离开的对面是什么？）。 - Ziggy

Answer 4

这有点取决于你使用的编程语言，但是在Java中，你可以创建一个名为Pair的类，并重写equals和hashcode方法。使equals方法返回true，如果x1 == x2或y1 == y2。 然后只需创建一个HashSet<Pair>并添加所有的成对元素。最终集合中将包含根据你的相等定义而唯一的所有成对元素。

- Irene Papakonstantinou

---

当您覆盖 equals 和 hashcode 时，插入的时间复杂度是多少？ - marshall

我认为这里未明确说明的问题是如何编写hashcode以满足定义。 - loopbackbee