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.