Расстояние между координатами в Big-oh of M time

Question

У меня есть массив координат, т.е. каждый индекс содержит (x, y) координаты. Я хочу понять, что если какая-либо из координат находится в одной строке или столбце. Задача состоит в том, чтобы сделать в одном цикле, где M - длина массива. Я старался, но, похоже, не мог сделать это, не используя две петли. Просто нужна помощь с алгоритмом.

Редактировать: В основном проблема в том, что у меня есть M штук на плате N на N. Каждый кусок может перемещаться по вертикали и по горизонтали любым числом. Просто хочу понять, что если какая-либо часть может атаковать любую другую вещь.

Answer 1

Это element distinctness/uniqueness problem, который имеет сложность O (MLogm) в общем случае (то есть сортировку).

Если нет ограничений памяти, вы можете использовать хэш-таблицу для Y и X-координату, в этом случае один проход через массив решает проблему

Edit: Для ограниченного борта это проще использовать булеву массив длина N для горизонталей и вертикалей. Сложность времени O (M), потребление памяти O (N)

for every rook: 
    if Horiz[rook.Y] then 
     two rooks share horizontal 
    if Vert[rook.X] then 
     two rooks share the same vertical 
    Horiz[rook.Y] = True 
    Vert[rook.X] = True