首页 > 代码库 > [LeetCode#73]Set Matrix Zeroes
[LeetCode#73]Set Matrix Zeroes
The problem:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
My analysis:
This is a very typical quesition in metricing our understanding about matrix.
The main idea is that :
We could not base on the changed columns or rows(have already been set to 0), to make our decision whether to reset a row or column. We must first scan the matrix, and then record the information(rows and columns needed to be reset) separately.
Thus, we could have 3 options:
1. use a flag matrix, which is the size of m * n.
2. use a flag array for each row, and a flag array for each column, which is is the size of m + n.
3. use two variable to store first row and first column‘s indicator respectively. Then, use first row and first column as indicator array for rows(2..n), columns(2..n). O(1) .
Note: the first row‘s information would not be lost, since if there is a zero in the column (include the column in the first row), the elemet of the first row would be soonerly zeroed.
The solution 3 is the most elegant and concise one. But when we scan the matrix, and reset the matrix, we shuld be very clear about the start point.
1. For scan. We should start from first row and first column, cause the first row also have the information about which row needs to be zeroed, not just indicate the column should be zeroed (which we have already done).
2. For reset. We should start form second row and first column, cause we have already use first row and first column for indicator purpose.
My solution:
public class Solution { public void setZeroes(int[][] matrix) { if (matrix.length == 0) return; boolean first_row_zero = false; //used to record if the first row needed to be set to zero. boolean first_column_zero = false; for (int i = 0; i < matrix.length; i++) { if (matrix[i][0] == 0) first_column_zero = true; } for (int j = 0; j < matrix[0].length; j++) { if (matrix[0][j] == 0) first_row_zero = true; } for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < matrix.length; i++) { //note: must start from second row and second column, Do not change first row or column. if (matrix[i][0] == 0) { for (int j = 1; j < matrix[0].length; j++) matrix[i][j] = 0; } } for (int j = 1; j < matrix[0].length; j++) { if (matrix[0][j] == 0) { for (int i = 1; i < matrix.length; i++) matrix[i][j] = 0; } } if (first_row_zero == true ) { for (int j = 0; j < matrix[0].length; j++) matrix[0][j] = 0; } if (first_column_zero == true) { for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0; } }}
[LeetCode#73]Set Matrix Zeroes