Матрица, алгоритм интервью, вопрос

Question

Это был один из моих вопросов на собеседовании.

У нас есть матрица, содержащая целые числа (диапазон не указан).Матрица случайно заполняется целыми числами.Нам нужно разработать алгоритм, который находит те строки, которые точно соответствуют столбцу (столбцам).Нам нужно вернуть номер строки и номер столбца для совпадения.Порядок соответствия элементов одинаков.Например, если i-я строка соответствует j-му столбцу, а i-я строка содержит элементы - [1,4,5,6,3].Тогда j-й столбец также будет содержать элементы - [1,4,5,6,3].Размер nx n.Мое решение:

RCEQUAL(A,i1..12,j1..j2)// A is n*n matrix
if(i2-i1==2 && j2-j1==2 && b[n*i1+1..n*i2] has [j1..j2])
   use brute force to check if the rows and columns are same.
if (any rows and columns are same)
   store the row and column numbers in b[1..n^2].//b[1],b[n+2],b[2n+3].. store row no,
                                                 // b[2..n+1] stores columns that 
                                                 //match with row 1, b[n+3..2n+2] 
                                                 //those that match with row 2,etc..

else
   RCEQUAL(A,1..n/2,1..n/2);
   RCEQUAL(A,n/2..n,1..n/2);
   RCEQUAL(A,1..n/2,n/2..n);
   RCEQUAL(A,n/2..n,n/2..n);

Принимает O (n ^ 2).Это правильно?Если правильно, есть ли более быстрый алгоритм?

Answer 1

вы можете построить три из данных в строках.тогда вы можете сравнить столбцы с три.

это позволит выйти, как только начало столбца не совпадет ни с одной строкой.также это позволит вам проверить столбец по всем строкам за один проход.

конечно, трия наиболее интересна, когда n велико (установка trie для небольшого n не стоит) и когда есть много строк и столбцов, которые совершенно одинаковыно даже в худшем случае, когда все целые числа в матрице различны, структура допускает четкий алгоритм ...

Answer 2

Вы могли бы ускорить средний случай, вычислив сумму для каждой строки / столбца и сузив свое сравнение методом грубой силы (что вы должны сделать в конечном итоге) только для строк, которые соответствуют суммам столбцов.

Это не увеличивает наихудший случай (все имеют одинаковую сумму), но если ваш ввод действительно случайный, это "не произойдет": -)

Answer 3

Если матрица действительно случайная ...

Вы можете создать список указателей на столбцы, отсортированный по первому элементу.Затем создайте аналогичный список строк, отсортированных по их первому элементу.Это займет O (n * logn).

Затем создайте индекс в каждом отсортированном списке, инициализированном 0. Если первые элементы совпадают, вы должны сравнить всю строку.Если они не совпадают, увеличьте индекс индекса с самым низким начальным элементом (либо перейдите к следующей строке, либо к следующему столбцу).Поскольку каждый индекс циклически изменяет от 0 до n-1 только один раз, у вас есть не более 2 * n сравнений, если только все строки и столбцы не начинаются с одного и того же числа, но мы назвали матрицу случайных чисел.для сравнения строк / столбцов в худшем случае n, но ожидается, что оно будет в среднем O (1) со случайными данными.

Итак, 2 вида O (nlogn) и сканирование 2 * n* 1 дает ожидаемое время выполнения O (nlogn).Это конечно предполагает случайные данные.В худшем случае все еще будет n ** 3 для большой матрицы с большинством элементов одинакового значения.

Answer 4

Не глядя на ваш алгоритм или любой из подходов в предыдущих ответах, но поскольку матрица имеет n ^ 2 элементов для начала, я не думаю, что есть метод, который делает это лучше:)

Answer 5

Это может работать только на неособых матрицах (не уверен), но ...

Пусть A - квадратная (и, возможно, неособая) матрица NxN.Пусть A 'будет транспонированием A. Если мы создадим матрицу B так, чтобы она была горизонтальной конкатенацией A и A' (другими словами [A A ']) и поместили ее в форму RREF, мы получим диагональ на всехединицы в левой половине и квадратная матрица в правой половине.

Пример:

A = 1 2
    3 4

A'= 1 3
    2 4

B = 1 2 1 3
    3 4 2 4

rref(B) = 1  0 0   -2
          0  1 0.5 2.5

С другой стороны, если столбец A равен строке A, то столбецА будет равно столбцу А '.Затем мы получим еще один 1-й из столбцов правой половины rref (B).

Пример

A=
 1     2     3     4     5
 2     6    -3     4     6
 3     8    -7     6     9
 4     1     7    -5     3
 5     2     4    -1    -1

A'=
 1     2     3     4     5
 2     6     8     1     2
 3    -3    -7     7     4
 4     4     6    -5    -1
 5     6     9     3    -1

B = 
 1     2     3     4     5     1     2     3     4     5
 2     6    -3     4     6     2     6     8     1     2
 3     8    -7     6     9     3    -3    -7     7     4
 4     1     7    -5     3     4     4     6    -5    -1
 5     2     4    -1    -1     5     6     9     3    -1

rref(B)=
 1     0     0     0     0    1.000  -3.689  -5.921   3.080   0.495
 0     1     0     0     0        0   6.054   9.394  -3.097  -1.024
 0     0     1     0     0        0   2.378   3.842  -0.961   0.009
 0     0     0     1     0        0  -0.565  -0.842   1.823   0.802
 0     0     0     0     1        0  -2.258  -3.605   0.540   0.662

1.000 в строке top правая половина означает, что первый столбец A соответствует одному из его рядов.Тот факт, что 1.000 находится в крайнем левом столбце правой половины, означает, что это первая строка.