LeetCode 矩阵置零_矩阵 恰好k个1变为0

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:
输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

思路分析：对这种问题大致有两种思路，第一种时边标记边修改，第二种是全部标记后再次修改。
方法一：先将矩阵进行复制，在复制的矩阵查找为0的元素，在原矩阵中进行修改。（时间复杂度为O(n * m)级别，额外空间复杂度为O（n * m））

class Solution {
public:
	void setZeroes(vector<vector<int>>& matrix) {
		int rowNum = matrix.size();
		int colNum = matrix[0].size();
		vector<vector<int>> tempMatrix = matrix;//复制
		for (int row = 0; row < rowNum; ++row){
			for (int col = 0; col < colNum; ++col){
				if (tempMatrix[row][col] == 0){//在复制的矩阵的进行查找
					//在原矩阵中进行修改
					for (int i = 0; i < colNum; ++i){//row行清零
						matrix[row][i] = 0;
					}
					for (int i = 0; i < rowNum; ++i){//col列清零
						matrix[i][col] = 0;
					}
				}
			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：先遍历一遍矩阵，将所有需要清零的行、列保存好，然后在进行清零。（时间复杂度为O(n * m)级别，额外空间复杂度为O（n + m））

class Solution {
public:
	void setZeroes(vector<vector<int>>& matrix) {
		int rowNum = matrix.size();
		int colNum = matrix[0].size();
		vector<bool> rowFlag(rowNum, false);//行标记
		vector<bool> colFlag(colNum, false);//列标记
		for (int row = 0; row < rowNum; ++row){
			for (int col = 0; col < colNum; ++col){
				if (matrix[row][col] == 0){//标记行、列
					rowFlag[row] = true;
					colFlag[col] = true;
				}
			}
		}
		for (int row = 0; row < rowNum; ++row){//对标记的行清零
			if (rowFlag[row]){
				for (int i = 0; i < colNum; ++i){//row行清零
					matrix[row][i] = 0;
				}
			}
			
		}
		for (int col = 0; col < colNum; ++col){//对标记的列清零
			if (colFlag[col]){
				for (int i = 0; i < rowNum; ++i){//col列清零
					matrix[i][col] = 0;
				}

			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法二优化版

class Solution {
public:
	void setZeroes(vector<vector<int>>& matrix) {
		int rowNum = matrix.size();
		int colNum = matrix[0].size();
		vector<bool> rowFlag(rowNum, false);//行标记
		vector<bool> colFlag(colNum, false);//列标记
		for (int row = 0; row < rowNum; ++row){
			for (int col = 0; col < colNum; ++col){
				if (matrix[row][col] == 0){//标记行、列
					rowFlag[row] = true;
					colFlag[col] = true;
				}
			}
		}
		for (int row = 0; row < rowNum; ++row){
			for (int col = 0; col < colNum; ++col){
				if (rowFlag[row] || colFlag[col]){//如果行或者列被标记了
					matrix[row][col] = 0;
				}
			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法三：采用不同的标记法，边找边修改。（时间复杂度为O(n * m)级别，额外空间复杂度为O（1））

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = 0;
        if(rows!=0){
            cols = matrix[0].size();
        }
        for(int i = 0;i < rows; i++){
            for(int j  = 0;j < cols; j++){
                if(matrix[i][j]==0){//找到等于0的元素
                    for(int k =0; k<cols;k++){//对第i行非0元素标记为*
                        if(matrix[i][k]!=0){
                            matrix[i][k]='*';
                        }
                    }
                    for(int k =0; k<rows;k++){//对第j列非0元素标记为*
                        if(matrix[k][j]!=0){
                            matrix[k][j]='*';
                        }
                    }
                }
            }
        }
        for(int i =0; i < rows; i++){//将*修改回0
            for(int j = 0; j <cols; j++){
                if(matrix[i][j]=='*')
                    matrix[i][j] = 0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32