This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Topic describes
The matrix zero
Write an algorithm to zero the rows and columns of an M by N matrix if any element is zero.
Example 1:
,1,1 input: [[1], [1, 1], [1,1,1]] output: [[1, 1], [0, 0], [1, 1]]Copy the code
Example 2:
,1,2,0 input: [[0], [3,4,5,2], [1,3,1,5]] output: [,0,0,0 [0], [0,4,5,0], [0,3,1,0]]Copy the code
Thought analysis
First, the simplest solution, namely brute force cracking, uses a List
List to record all the subscripts that are 0 for the position of the matrix, and then iterates the values in the matrix and sets the row and column to 0 respectively. The time complexity of this solution is O(m∗n){O(m*n)}O(m∗n), The space complexity is also O(m){O(m)}O(m) or O(n){O(n)}O(n).
Another way to think about it is, the whole matrix is always going to be whether there are zeros in the rows and columns, and we can apply that uniformly to the first row and the first column. We first judge whether the first row and first column have 0, and record them using two variables. The time complexity of this solution is O(m∗n){O(m*n)}O(m∗n), and the space complexity is also O(1){O(1)}O(1).
The code shown
Solution 1: brute force cracking, first the matrix for 0 coordinates are recorded, and finally traversal, the corresponding position is set to 0. Time complexity is O (m ∗ (n) (m * n)} {O O (m ∗ n), space complexity is O (m) (m)} {O O (m) or O (n) (n)} {O O (n).
public void setZeroes(int[][] matrix) {
List<int[]> list = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) { //matrix.length = 4
for (int j = 0; j < matrix[0].length; j++){if (matrix[i][j] == 0){
list.add(new int[]{i,j}); }}}for (int i = 0; i < list.size(); i++){int[] temp = list.get(i);
int a1 = temp[0];
for (int j = 0; j < matrix[0].length; j++){ matrix[a1][j] =0;
}
int a2 = temp[1];
for (int k = 0; k < matrix.length; k++){ matrix[k][a2] =0; }}Copy the code
Method 2: The time complexity of the above solution is O(m∗n){O(m*n)}O(m∗n), and the space complexity is O(m){O(m)}O(m) or O(n){O(n)}O(n). The time complexity cannot be simplified, because it needs to be iterated, but the space complexity can be optimized. Because we can all migrate to row 1, column 1, but first remember if row 1 / column 1 has a 0, and then do something about it.
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean firstCol = false; / / column
boolean firstRow = false; / / line
for (int i = 0; i < m; i++) {
if (matrix[i][0] = =0) {
firstCol = true; // The first column has 0
break; }}for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRow = true; // The first line has 0
break; }}for (int i = 1; i < m; i++) { // Assign 0 to the first row or column
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0; }}}for (int i = 1; i < m; i++) { / / column
for (int j = 1; j < n; j++) { / / line
if (matrix[i][0] = =0 || matrix[0][j] == 0){
matrix[i][j] = 0; }}}if (firstRow){
for (int i = 0; i < n; i++){ matrix[0][i] = 0; }}if (firstCol){
for (int j = 0; j < m; j++){ matrix[j][0] = 0; }}}Copy the code
conclusion
When solving this kind of problems, we can first try brute force cracking, and then optimize the space complexity by combining the characteristics of matrix and problems.