题目描述:
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
解析:
1.检查并标记第一行和第一列是否有零(firstColHasZero和firstRowHasZero)
2.使用第一行和第一列,来标记其余行列是否含有零
3.接下来,利用第一行和第一列的标零情况,将matrix中的数字标零
4.最后,处理第一行和第一列
如果firstColHasZero等于true,将第一列全设为零
如果firstRowHasZero等于true,将第一行全设为零
Java:
public void setZeroes(int[][] matrix) { boolean firstColHasZero = false; boolean firstRowHasZero = false; // 检查第一列是否有零 for(int i = 0; i < matrix.length; i++) { if(matrix[i][0] == 0) { firstColHasZero = true; } } // 检查第一行是否有零 for(int i = 0; i < matrix[0].length; i++) { if(matrix[0][i] == 0) { firstRowHasZero = true; } } // 使用第一行和第一列,来标记其余行列是否有零 for(int row = 1; row < matrix.length; row++) { for(int col = 1; col < matrix[0].length; col++) { if(matrix[row][col] == 0) { matrix[row][0] = 0; matrix[0][col] = 0; } } } // 接下来,利用第一行和第一列的标零情况,将matrix中的数字标零 for(int row = 1; row < matrix.length; row++) { for(int col = 1; col < matrix[0].length; col++) { if(matrix[row][0] == 0 || matrix[0][col] == 0) { matrix[row][col] = 0; } } } // 最后,处理第一行和第一列 // 如果firstColHasZero等于true,将第一列全设为0 if(firstColHasZero) { for(int i = 0; i < matrix.length; i++) { matrix[i][0] = 0; } } // 如果firstRowHasZero等于true,将第一行全设为0 if(firstRowHasZero) { for(int i = 0; i < matrix[0].length; i++) { matrix[0][i] = 0; } } return; }
JavaScript:
var setZeroes = function(matrix) { let firstColHasZero = false; let firstRowHasZero = false; // 检查第一个列是否有零 for(let i = 0; i < matrix.length; i++) { if(matrix[i][0] === 0) { firstColHasZero = true; } } // 检查第一行是否有零 for(let i = 0; i < matrix[0].length; i++) { if(matrix[0][i] === 0) { firstRowHasZero = true; } } // 使用第一行和第一列,来标记其余行列是否有零 for(let row = 1; row < matrix.length; row++) { for(let col = 1; col < matrix[0].length; col++) { if(matrix[row][col] === 0) { matrix[row][0] = 0; matrix[0][col] = 0; } } } // 接下来,利用第一行和第一列的标零情况,将matrix中的数字标零 for(let row = 1; row < matrix.length; row++) { for(let col = 1; col < matrix[0].length; col++) { if(matrix[row][0] === 0 || matrix[0][col] === 0) { matrix[row][col] = 0; } } } // 最后,处理第一行和第一列 // 如果firstColHasZero等于零,将第一列全设为零 if(firstColHasZero) { for(let i = 0; i < matrix.length; i++) { matrix[i][0] = 0; } } // 如果firstRowHasZero等于零,将第一行全设为零 if(firstRowHasZero) { for(let i = 0; i < matrix[0].length; i++) { matrix[0][i] = 0; } } return matrix; };