成都建设厅官方网站,网站建设业务渠道,广州外贸网站建设 open,ps 如何做网站从0开始的秋招刷题路#xff0c;记录下所刷每道题的题解#xff0c;帮助自己回顾总结
73. 矩阵置零
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1#xff1a;
输入#xff1a;mat…从0开始的秋招刷题路记录下所刷每道题的题解帮助自己回顾总结
73. 矩阵置零
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1
输入matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]
示例 2
输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示 m matrix.length n matrix[0].length 1 m, n 200 −231-2^31−231 matrix[i][j] 231−12^31 - 1231−1
进阶 一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。 你能想出一个仅使用常量空间的解决方案吗
方法一 思路用两个set分别记录需要置0的行和需要置0的列。第一次遍历矩阵时若发现一个元素为0则将其行和列值分别加入到两个set中。第二次遍历矩阵时将行set中的行全部置0将列set中的列全部置0。
public void setZeroes(int[][] matrix) {if(matrix null || matrix.length 0)return;int m matrix.length, n matrix[0].length;SetInteger row new HashSetInteger();SetInteger col new HashSetInteger();for(int i 0; i m; i){for(int j 0; j n; j){if(matrix[i][j] 0){row.add(i);col.add(j);}}}for(int i : row){for(int j 0; j n; j)matrix[i][j] 0;}for(int j : col){for(int i 0; i m; i)matrix[i][j] 0;}
}时间复杂度O(m×n) 空间复杂度O(mn) 最坏情况是矩阵中全部元素为0的情况这时两个set的大小分别为m和n。
方法二 思路不用额外空间让首行和首列记录某列和某行是否有0
算法步骤 首先用两个布尔类型变量firstRow和firstCol分别记录矩阵的首行和首列中是否有0 遍历除首行和首列外的所有元素若元素matrix[i][j]为0则将它对应的首行和首列中的元素matrix[i][0]和matrix[0][j]置为0意为此行和列后续需要被置0由于修改后首行和首列是否有0的信息会被破坏掉因此需要有之前的步骤一 遍历首行和首列若发现首行中有元素为0则将此元素所处的列全部置0若发现首列中有元素为0则将此元素所处的行全部置0。 根据步骤一的布尔类型变量firstRow和firstCol来判断首行和首列是否需要被置0。
public void setZeroes(int[][] matrix) {if(matrix null || matrix.length 0)return;int m matrix.length, n matrix[0].length;boolean firstRow false, firstCol false;//步骤一for(int i 0; i m; i){if(matrix[i][0] 0)firstCol true;}for(int j 0; j n; j){if(matrix[0][j] 0)firstRow true;}//步骤二for(int i 1; i m; i){for(int j 1; j n; j){if(matrix[i][j] 0){matrix[i][0] 0;matrix[0][j] 0;}}}//步骤三for(int i 1; i m; i){if(matrix[i][0] 0){for(int j 0; j n; j)matrix[i][j] 0;}}for(int j 1; j n; j){if(matrix[0][j] 0){for(int i 0; i m; i)matrix[i][j] 0;}}//步骤四if(firstRow){for(int j 0; j n; j)matrix[0][j] 0;}if(firstCol){for(int i 0; i m; i)matrix[i][0] 0;}
}时间复杂度O(m×n) 空间复杂度O(1)
