Найти уникальную пару пар

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) a .

Обратите внимание, что такая пара точек не существует только тогда, когда все точки лежат на одной прямой, параллельной оси. Определите эту строку двумя первыми точками, а затем для каждой новой точки проверьте, лежит ли она на той же линии или нет.

Answer 2

Если первые две пары (x1, y1) и (x1, y2) [y1 != y2], затем из оставшегося списка пар, если вы обнаружите какие-либо x != x1, его соответствующий y должен либо не может быть равен y1 или не равна y2.

Answer 3

Вторая попытка:

Вам понадобится: 1 граф и 1 целое i.

Iterate над вашими парами, помещая их в направленном граф, как вы идете, такой, что для каждого (x, y) есть направленное ребро x -> y. После добавления ребра к графику проверьте обе вершины:

Если вершины x и y имеют нулевую степень, приращение i. В противном случае для каждой вершины, имеющей степень ровно 2, декремент i.

До тех пор, пока i > 0 существует пара пар, которые удовлетворяют вашему состоянию.

Answer 4

Это немного зависит от языка, который вы используете, но на Java вы можете создать класс Pair и переопределить equals и hashcode. Сделайте equals return true, если x1 == x2 ИЛИ y1 == y2. Затем просто создайте HashSet<Pair> и добавьте все свои пары. То, что будет в конце в конце, будет все четкие пары, согласно вашему определению равенства.