Эффективный алгоритм проверки повторяющихся строк в матрице

Задана матрица M целых чисел. Проверьте, совпадают ли две строки в матрице. Дайте оптимальный подход.

Example:
[{1, 2, 3},
 {3, 4, 5},
 {1, 2, 3}]

В приведенной выше матрице строки 1 и 3 идентичны.

Возможное Решение: 

Given a matrix, we can convert each row in a string (example using to_string()
method of C++ and concatenating each element in a row to a string). We do this
for every row of the matrix, and insert it in a table that is something like
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time
for an mxn matrix.

Могу ли я сделать лучше, чем это ? Или, вышеописанный метод имеет какой-то изъян ?

2 6
algorithm matrix time-complexity

2 ответа:

Ваш метод работает, но вы ошибаетесь в его сложности.

Во-первых, тестирование, если элемент находится в std::map имеет сложность O(log(n) * f), где n - количество элементов в карте и f - верхняя граница времени, необходимого для сравнения любых двух элементов, вставленных/искомых в карту.

В вашем случае каждая строка имеет длину m, поэтому сравнение любых двух элементов в карте стоит O(m). Таким образом, общая сложность вашего метода составляет:

O(n * log(n) * m) для вставки n строк в карту.

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

В C++ для этого можно использовать unordered_set.

6

В зависимости от размера матрицы, преобразование всего в строку кажется довольно большой тратой времени и пространства.

Почему бы не вычислить вероятный уникальный хэш для каждой строки. Например, вы можете вычислить битовое значение или всех записей, а затем сохранить этот хэш вместе с индексом строки в multimap. Когда вы проходите через каждую строку, вы вычисляете ее хэш, а затем проверяете, существует ли этот хэш уже. Если это так, сравните вашу строку с другими строками с тем же хэшем, чтобы увидеть если они равны.

Это не имеет лучшей сложности Big-O, но почти наверняка имеет меньшую константу и использует меньше пространства.

0