大连手机网站开发,江苏江都建设集团有限公司网站,自己做网站要买什么,wordpress顶部修改题目链接
矩阵置零
题目描述 注意点
使用 原地 算法
解答思路
思路是需要存储每一行以及每一列是否有0#xff0c;因为要尽可能使用更少的空间#xff0c;且新设置为0的格子不能对后续的判断产生影响#xff0c;所以要在原有矩阵上存储该信息先用两个参数存储第一行和第…题目链接
矩阵置零
题目描述 注意点
使用 原地 算法
解答思路
思路是需要存储每一行以及每一列是否有0因为要尽可能使用更少的空间且新设置为0的格子不能对后续的判断产生影响所以要在原有矩阵上存储该信息先用两个参数存储第一行和第一列是否有0再用第一行和第一列分别存储相应列和相应行中是否有0也就是matrix[i][0]存储第i行是否有0matrix[0][j]存储第j列是否有0这样做相当于只用了2个额外空间后续再根据matrix[i][0]和matrix[0][j]的信息更新matrix[i][j]的值最后再更新第一行和第一列的值即可
代码
class Solution {public void setZeroes(int[][] matrix) {int row matrix.length;int col matrix[0].length;// 存储第一行和第一列是否有0int flag_row 0;int flag_col 0;while (flag_row row matrix[flag_row][0] ! 0) {flag_row;}while (flag_col col matrix[0][flag_col] ! 0) {flag_col;}// 第一行存储每一列是否有0第一列分别存储每一行是否有0for (int i 1; i row; i) {for (int j 1; j col; j) {if (matrix[i][j] 0) {matrix[i][0] 0;matrix[0][j] 0;}}}for (int i 1; i row; i) {for (int j 1; j col; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}if (flag_row ! row) {for (int i 0; i row; i) {matrix[i][0] 0;}}if (flag_col ! col) {for (int j 0; j col; j) {matrix[0][j] 0;}}}
}关键点
除第一行和第一列使用额外参数存储是否有0外其余行和列是否有0都存储在第一行和第一列中
