Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
对于Space: O(m + n)的方法比较好想。主要是O(1)的解法比较有趣,我们把矩阵第一行和第一列当做mark,来判断当前行和列是否需要置0。在这之前需要两个变量先判断矩阵第一行和第一列是否需要置0。
public class Solution { //Time: O(m*n) Space: O(1) public void setZeroes(int[][] matrix) { if (matrix == null || matrix.length == 0) { return; } //mark first row and col boolean zeroFirstRow = false; for (int i = 0; i < matrix[0].length; i++) { if (matrix[0][i] == 0) { zeroFirstRow = true; break; } } boolean zeroFirstCol = false; for (int i = 0; i < matrix.length; i++) { if (matrix[i][0] == 0) { zeroFirstCol = true; break; } } for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < matrix[0].length; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } //zero for (int i = 1; i < matrix.length; i++) { if (matrix[i][0] == 0) { zeroRow(matrix, i); } } for (int i = 1; i < matrix[0].length; i++) { if (matrix[0][i] == 0) { zeroCol(matrix, i); } } if (zeroFirstRow) { zeroRow(matrix, 0); } if (zeroFirstCol) { zeroCol(matrix, 0); } } private void zeroRow(int[][] matrix, int row) { for (int i = 0; i < matrix[0].length; i++) { matrix[row][i] = 0; } } private void zeroCol(int[][] matrix, int col) { for (int i = 0; i < matrix.length; i++) { matrix[i][col] = 0; } } }
No comments:
Post a Comment