Алгоритм для удаления всех «плохих» столбцов и строк

Question

Данная байт-матрица (все значения имеют 1 бит в памяти), назовем ее «raw» или «bad» столбца, если в ней есть хотя бы один нуль. Найти алгоритм, который принимает O (1) дополнительную память.

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

Answer 1

Предполагая, что A - это байт-матрица, предоставленная вам. Это решение использует постоянное дополнительное пространство. Используйте первую строку и столбец в матрице, чтобы действовать как флаг. Требуется только один дополнительный флаг (здесь r1) для строки1.

void setZeroes(vector<vector<int> > &A) { 
    int m = A.size(); 
    int n = A[0].size(); 
    int r1 = 1; //row1 
    for(int j = 0; j < n; j++){ 
     r1 *= A[0][j]; 
    } 
    for(int i = 1; i < m; i++){ //first row skipped 
     for(int j = 0; j < n; j++){ 
      A[0][j] *= A[i][j]; //Marking Colm 
      A[i][0] *= A[i][j]; //Marking rows, skipping row#1 
     } 
    } 
    for(int i = 1; i < m; i++){ 
     for(int j = 1; j < n; j++){ 
      A[i][j] = A[0][j] * A[i][0]; 
     } 
    } 
    //At last, update colm1. 
    for(int j = 1; j < m; j++){ 
     A[j][0] *= A[0][0]; 
    } 
    //At last, update row1. 
    for(int j = 0; j < n; j++){ 
     A[0][j] *= r1; 
    } 
} 

Answer 2

Этот алгоритм использует O (1) пространство. Ниже приведены этапы:

1. Найти первую строку со всеми 1 значениями. Если такой строки нет, поэтому все строки содержат по крайней мере один 0, поэтому вся матрица должна стать 0s. Держите индекс строки в переменной I.

2. Используйте I-я строка как флаг, чтобы сохранить значение для каждого столбца, то есть & весь столбец и сохранить в I-й строке.

3. & вся строка, за исключением I-го и заданного значения, для элементов этой конкретной строки, т.е. возьмите 1-ю строку, если она имеет хотя бы одну 0, заданную целую строку до 0, иначе оставить строку со всеми 1-м, взять вторую строку и так далее кроме меня строка.
4. & I-я строка для всех других строк, то есть A[i][j] &= A[I][j] для всех i <> I и j=0,1,...,A[I].length-1.

Thats all !!!

В качестве примера мы имеем

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

После 1-го шага мы найдем = 1 во втором ряду.

Тогда мы изменяем 2-ю строку только матрица будет стала после того, как 2-й стадии (она изменила 1-й, 2-й, 4-й и последний элемент 0, потому что нашел 0s в том, что колонки):

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

После шага 3 матрица стала (мы установим 0s к строкам, который имеет по меньшей мере один 0 excep 2-я строка):

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

После шага 4 матрица стала следующим образом (мы делаем & операции через все столбцы):

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

То есть матрица мы ищем.