> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/73.-set-matrix-zeroes.md).

# 73. Set Matrix Zeroes

## problem description

Given a *m* x *n* matrix, if an element is 0, set its entire row and column to 0. Do it [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm).

**Example 1:**

```
Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
```

**Example 2:**

```
Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
```

## algorithm thought

这个题目不是很难，但是LeetCode限制了我们，希望我们使用O(1)的空间复杂度，然后DO IT IN-PLACE。于是我将第一行和第一列定义为标志位，从2行2列开始遍历，如果为0，将为0的那行和列的第一位设置为0标志位。之后再次遍历一遍第一行和第一列，将有标志位的那一行或者一列置为零

## code

```cpp
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0)
            return ;
        bool row=false,col=false;
        //判断第一列是否有0
        for(int i=0;i<matrix.size();++i)
            if(matrix[i][0]==0){
                row=true;
                break;
            }
        //判断第一行是否有0
        for(int i=0;i<matrix[0].size();++i)
            if(matrix[0][i]==0){
                col=true;
                break;
            }
        if(row||col)
            matrix[0][0]=0;
        //如果某位是0，将对应的第一行第一列都设置为0
        for(int i=1;i<matrix.size();++i){
            for(int j=1;j<matrix[0].size();++j){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //如果第一列末位是0，将这一行所有的设置为0
        for(int i=1;i<matrix.size();++i){
            if(matrix[i][0]==0){
                for(int j=1;j<matrix[0].size();++j){
                    matrix[i][j]=0;
                }
            }
            if(row)
                matrix[i][0]=0;
        }
        //如果第一行末位是0，将这一列所有的设置为0
        for(int j=1;j<matrix[0].size();++j){
            if(matrix[0][j]==0){
                for(int i=1;i<matrix.size();++i){
                    matrix[i][j]=0;
                }
            }
            if(col)
                matrix[0][j]=0;
        }
    }
};
```

## algorithm analysis

这类题目，无论你算法多么巧妙，时间复杂度都会是O(n²)，但是这里空间复杂度被限制到了O(1)，有很大提升。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/73.-set-matrix-zeroes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.