Можем ли мы вычислить это менее чем за O (n * n) ... (nlogn или n)

Question

Это вопрос, заданный мне очень и очень известным MNC. Вопрос в следующем ...

Введите двумерный массив N * N, состоящий из 0 и 1. Если A (i, j) = 1, то все значения, соответствующие i-й строке и j-му столбцу, будут равны 1. Если уже есть 1, он остается равным 1.

В качестве примера, если у нас есть массив

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

мы должны получить вывод как

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

Входная матрица заполнена редко.

Возможно ли это менее чем за O (N ^ 2)?

Дополнительного места не было, было другое условие. Я хотел бы знать, если есть способ достичь сложности, используя пробел <= O (N). </p>

P.S .: Мне не нужны ответы, которые дают мне сложность O (N * N). Это не домашняя проблема. Я много пытался и не смог найти правильного решения, и подумал, что смогу найти здесь некоторые идеи. Оставьте печать в стороне для сложности

Моя грубая идея состояла в том, чтобы, возможно, динамически исключить количество пройденных элементов, ограничив их до 2N или около того. Но я не мог получить правильное представление.

Answer 1

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

edit: На самом деле, это то же самое, что и у Энди.

Answer 2

Это полностью зависит от вашей структуры входных данных.Если вы передадите свою матрицу (1 с и 0 с) как двумерный массив, вам нужно пересечь ее, и это O (N ^ 2).Но поскольку ваши данные редки, если вы передаете только 1 в качестве входных данных, вы можете сделать это так, чтобы выходной сигнал был O (M), где M - это не количество ячеек, а число ячеек.Было бы что-то похожее на это (псевдокод ниже):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

Answer 3

Если ваша матрица разрежена, сложность во многом зависит от входного кодирования и, в частности, не очень хорошо измеряется в NN ² или что-то в этом роде, но с точки зрения N, ваша сложность ввода M ^в и ваша сложность вывода M ^out .Я бы ожидал что-то вроде O (N + M ^в + M ^из ), но во многом в зависимости от кодировки и трюков, которые вы можете играть с ним.