【LeetCode】 73. 矩阵置零空间O(1)

古城微笑少年丶 2021-06-10 20:38 297阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

1.  空间复杂度为O(mn)的解决方案很容易思考出来
2.  空间复杂度为O(m+n)的解决方案也比较容易，创建两个数组长度分别为m和n，用来记录行或者列中出现过的0
3.  空间复杂度为O(1)的解决方案就是在 2 的基础上，把这个数组放在了矩阵中来记录

### 我的思路 ###

1.  遍历找到第一个 0，并且把这一行和这一列作为记录有 0 的行和列  
    ![在这里插入图片描述][20200224135104352.png]  
    找到的第一个 0 在第一行，第二列，所以第一行和第二列，就作为记录的行和列  
    ![在这里插入图片描述][20200224135237382.png]
2.  继续向下找，每找到 0 ，就在这一行中进行记录，  
    ![在这里插入图片描述][20200224135606588.png]
3.  记录好了之后，先置零列  
    ![在这里插入图片描述][20200224140854171.png]
4.  再置零行  
    ![在这里插入图片描述][20200224140234492.png]

### 代码 ###

class Solution { 
        public void setZeroes(int[][] matrix) { 
            int rows = matrix.length;
            int cols = matrix[0].length;
            int recRow = -1;
            int recCol = -1;
            // 把有 0 的行和列都记录到 recRow 和 recCol 中
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (matrix[i][j] == 0) { 
                        if (recRow == -1 && recCol == -1) { 
                            recRow = i;
                            recCol = j;
                        } else { 
                            matrix[recRow][j] = 0;
                            matrix[i][recCol] = 0;
                        }
                    }
                }
            }
            // 如果矩阵中没有 0 ，就直接返回
            if (recCol == -1 && recRow == -1) return;
            // 将 recRow 记录的所有的行设置为 0
            for (int j = 0; j < cols; j++) { 
                if (j != recCol) { 
                    if (matrix[recRow][j] == 0) { 
                        for (int i = 0; i < rows; i++) { 
                            matrix[i][j] = 0;
                        }
                    } else { 
                        matrix[recRow][j] = 0;
                    }
                }
            }
            // 将 recCol 记录的所有的列设置为 0
            for (int i = 0; i < rows; i++) { 
                if (i != recRow) { 
                    if (matrix[i][recCol] == 0) { 
                        for (int j = 0; j < cols; j++) { 
                            matrix[i][j] = 0;
                        }
                    } else { 
                        matrix[i][recCol] = 0;
                    }
                }
            }
    
        }
    }

![在这里插入图片描述][20200224140322531.png]

[Link 1]: https://leetcode-cn.com/problems/set-matrix-zeroes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/af9693e703fd48d991f2423323b48ccc.png
[20200224135104352.png]: /images/20210529/42b6f15b8bc6423e8e5f0cdf8c6dbbef.png
[20200224135237382.png]: /images/20210529/e0d917ac67be4097a3880faa2fbf7ff5.png
[20200224135606588.png]: /images/20210529/3a5c945b1f1f42719595b316b875777b.png
[20200224140854171.png]: /images/20210529/14a38045e2124db4aa728483e559b33c.png
[20200224140234492.png]: /images/20210529/34d3e91af95849f1afad40e64923a6b1.png
[20200224140322531.png]: /images/20210529/9783712439104b70bc2ff95a22d8c600.png