73. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

73. Установка нулей в матрице

Задана матрица m x n. Если ее элемент равен 0, то установите все элементы соответствующих столбца и строки в 0. Используйте константную память.

// C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

}

};

// Java

public class Solution {

public void setZeroes(int[][] matrix) {

}

}

РЕШЕНИЕ

обработка массивов

Анализ алгоритма

Проверим, содержит ли первая строка нули, занесем эту информацию в переменную FirstRow булевого типа. Аналогично проверим, содержит ли первый столбец нули, и занесем эту информацию в переменную FirstColumn булевого типа.

Теперь в matrix[i][0] занесем 0, если в i-ой строке содержится 0. Аналогично в matrix[0][j] занесем 0, если в j-ом столбце содержится 0. Для этого перебираем все элементы матрицы и если matrix[i][j] = 0, то устанавливаем matrix[0][j] = matrix[i][0] = 0.

Теперь имея информацию о присутствии нулей в каждой строке и каждом столбце, за один проход по матрице устанавливаем matrix[i][j] = 0, если только matrix[i][0] = 0 или matrix[0][j] = 0.

Если FirstRow = true, то обнуляем первую строку.

Если FirstColumn = true, то обнуляем первый столбец.

Реализация алгоритма

class Solution

{

public:

void setZeroes(vector<vector<int>>& matrix)

{

bool FirstColumn = false;

bool FirstRow = false;

int i, j;

//set first column zero or not

for(i = 0; i < matrix.size(); i++)

if(matrix[i][0] == 0)

{

FirstColumn = true;

break;

}

//set first row zero or not

for(i = 0; i < matrix[0].size(); i++)

if(matrix[0][i] == 0)

{

FirstRow = true;

break;

}

//mark zeros on first row and column

for(i = 1; i < matrix.size(); i++)

for(j = 1; j < matrix[0].size(); j++)

if(matrix[i][j] == 0)

{

matrix[i][0] = 0;

matrix[0][j] = 0;

}

//use mark to set elements

for(i = 1; i < matrix.size(); i++)

for(j = 1; j < matrix[0].size(); j++)

if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

//set first column and row

if(FirstColumn)

for(i = 0; i < matrix.size(); i++)

matrix[i][0] = 0;

if(FirstRow)

for(i = 0; i < matrix[0].size(); i++)

matrix[0][i] = 0;

}

};

Java реализация

public class Solution

{

public void setZeroes(int[][] matrix)

{

boolean FirstColumn = false;

boolean FirstRow = false;

int i, j;

//set first column zero or not

for(i = 0; i < matrix.length; i++)

if(matrix[i][0] == 0)

{

FirstColumn = true;

break;

}

//set first row zero or not

for(i = 0; i < matrix[0].length; i++)

if(matrix[0][i] == 0)

{

FirstRow = true;

break;

}

//mark zeros on first row and column

for(i = 1; i < matrix.length; i++)

for(j = 1; j < matrix[0].length; j++)

if(matrix[i][j] == 0)

{

matrix[i][0] = 0;

matrix[0][j] = 0;

}

//use mark to set elements

for(i = 1; i < matrix.length; i++)

for(j = 1; j < matrix[0].length; j++)

if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

//set first column and row

if(FirstColumn)

for(i = 0; i < matrix.length; i++)

matrix[i][0] = 0;

if(FirstRow)

for(i = 0; i < matrix[0].length; i++)

matrix[0][i] = 0;

}

}