Найти a, b, c, которые имеют свойство x [a] [b] = x [a] [c] = x [b] [c]

Question

У меня есть двумерный массив с именем x. Я хочу рассчитать все трехэлементные группы, в которых x[a][b] = x[a][c] = x[b][c], как можно быстрее, конечно. Мне не нужно знать эти элементы, мне нужно только количество этих групп.

Размер первого измерения этого массива равен размеру второго.

Я знаю решение грубой силы, оно имеет сложность O (n^2), где n - размер массива. Я предполагаю, что есть более быстрое решение, но я понятия не имею, как это выглядит.

Answer 1

Я не вижу ничего, кроме грубой силы.

Искать каждую строку для пары, затем проверьте x [b] [c] для этой пары.

Пусть массив будет NxN. Сравнивая каждый элемент строки с каждым другим элементом строки занимает

N choose 2 = N(N-1)/2 = O(N^2) 

сравнения, и вы должны сделать это для всех N строк, дающих O(N^3). Если ваш общий размер разговоров (M=N^2), то его O(N^(3/2)).

Answer 2

Я уверен, скотина решение сила будет O (^ 3 N)

Другое решение (кроме тривиального (0,0,0)) было бы поместить каждую пару в хэш используя его значение в качестве ключа. Затем найдите пары, которые соответствуют вашему критерию в пределах дубликатов.