Make writing a habit together! This is the 14th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

The title

** 73. Set the matrix to zero **

Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Please use the in place algorithm.

Example 1:

Input: matrix = [,1,1 [1], [1, 1], [1,1,1]] output: [[1, 1], [0, 0], [1, 1]]Copy the code

Example 2:

Input: matrix = [,1,2,0 [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

Tip:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Copy the code

Advanced:

An intuitive solution would be to use O(MN) extra space, but this is not a good solution. A simple improvement would be to use O(m + N) extra space, but this is still not the best solution. Can you come up with a solution that only uses constant space?

Answer key

Analysis of the problem solving

Their thinking

Use a marker variable record

We can further optimize method 2 by using only one marker variable to record whether the first column originally had a 0. Thus, the first element of the first column marks the occurrence of a 0 in the first row. But to prevent the first element of each column from being updated prematurely, we need to process the matrix elements in reverse order, starting with the last row.

The complexity of the

Time complexity O(M * N) Space complexity O(1)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i =0; i < m; i++) {
            if (matrix[i][0] = =0) {
                flagCol0 = true;
            }
            for (int j =1; j <n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0; }}}for (int i = m-1; i >=0; i--) {
            for (int j = 1; j<n; j++) {
                if (matrix[i][0] = =0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0; }}if (flagCol0) {
                matrix[i][0] = 0; }}}}Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • Force buckle 73. Matrix zero