поиск "двойных" совпадений в "трехмерном" массиве

Рейтинг: 1Ответов: 1Опубликовано: 03.02.2023

Имеется большой массив, в каждой строчке ровно три числа, каждое число 32битное. Вопрос - какой самый быстрый алгоритм поиска "двойных" совпадений ?

Например, если массив

1 2 33

1 3 5

2 3 8

2 7 33

2 33 1012

то найтись должны три строчки "1 2 33", "2 7 33" и "2 33 1012", так как "двойным" совпаденьем является "2" и "33". (естественно, нужно найти все-все различные имеющиеся совпаденья)

Пока что я это реализовал так: создаётся три вспомогательных массива. В первом числа в строках сортируются как мин-сред-макс, во втором мин-макс-сред, в третьем сред-макс-мин. Потом массивы объединяются в один, массив сортируется и идёт построчная сверка первых двух чисел.

Есть ли более быстрый и оптимальный алгоритм такового поиска ?!

алгоритм поиск
Источник: Stack Overflow на русском

Ответы

▲ 3

Я бы сделал через словарь:

  • все три сочетания цифр в отсортированном виде используются как ключи словаря, по которым добавляется текущая комбинация цифр
  • берутся значения этого словаря, в которых получилось больше одного элемента
    Вроде бы сложность O(1) должна получиться.
from collections import defaultdict

data = """\
1 2 33
1 3 5
2 3 8
2 7 33
2 33 1012""".split('\n')

d = defaultdict(list)
for line in data:
    numbers = tuple(sorted(line.split()))
    for i1, i2 in ((0, 1), (0, 2), (1, 2)):
        d[(numbers[i1], numbers[i2])].append(line)

for val in d.values():
    if len(val) > 1:
        print(val)

Вывод:

['1 2 33', '2 7 33', '2 33 1012']