#P4013. 矩阵置零
-
ID: 2220
Tried: 104
Accepted: 37
Difficulty: 4
矩阵置零
题目内容
给定一个 m×n的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法
输入描述
第一行两个整数m，n 接下来m行，每行n列，代表输入的矩阵。 每行的数字之间以空格分隔。
输出描述
输出操作后的矩阵。
样例1
输入
3 3
1 1 1
1 0 1
1 1 1
输出
1 0 1
0 0 0
1 0 1
样例2
输入
3 4
0 1 2 0
3 4 5 2
1 3 1 5
输出
0 0 0 0
0 4 5 0
0 3 1 0
提示
- m==matrix.length
- n==matrix[0].length
- 1<=m,n<=200
- −231<=matrix[i][j]<=231−1
矩阵零置换问题
题解思路
本题要求我们在一个 m × n 的矩阵中，如果某个元素为 0，则将其所在行和列的所有元素都设为 0。同时，需要使用原地算法，即不额外使用额外的存储空间（或尽可能减少额外空间的使用）。
我们可以采取如下方法：
-
第一遍遍历：标记零元素的位置
- 使用两个数组
row_flag和col_flag分别记录需要清零的行和列，大小分别为m和n。 - 遍历整个矩阵，找到
0位置时，将对应的row_flag[i]和col_flag[j]设为True。
- 使用两个数组
-
第二遍遍历：将行和列清零
- 再次遍历矩阵，如果当前行
i或列j被标记，则将matrix[i][j]置为0。
- 再次遍历矩阵，如果当前行
-
优化方案（使用矩阵本身的第一行和第一列作为标记）
- 由于
row_flag和col_flag额外占用O(m + n)空间，我们可以用矩阵的第一行和第一列来存储这些标记。 - 额外使用两个变量
row_zero和col_zero记录第一行和第一列是否需要清零，避免污染原始数据。 - 遍历矩阵时，使用
matrix[0][j]标记第j列是否需要清零，使用matrix[i][0]标记第i行是否需要清零。
- 由于
时间复杂度
- 我们需要遍历矩阵两遍，一次用于标记，一次用于清零，总共
O(2 * m * n)，即O(m * n)。
空间复杂度
- 使用额外数组
O(m + n)的方法：额外的行和列数组需要O(m + n)空间。 - 优化后使用原矩阵第一行和第一列：额外空间只需要
O(1)。
代码
Python 代码
class Solution:
def setZeroes(self, matrix):
if not matrix:
return
m, n = len(matrix), len(matrix[0])
row_zero = any(matrix[0][j] == 0 for j in range(n))
col_zero = any(matrix[i][0] == 0 for i in range(m))
# 使用第一行和第一列作为标记
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 根据标记清零
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 处理第一行
if row_zero:
for j in range(n):
matrix[0][j] = 0
# 处理第一列
if col_zero:
for i in range(m):
matrix[i][0] = 0
# 读取输入并处理
if __name__ == "__main__":
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
solution = Solution()
solution.setZeroes(matrix)
for row in matrix:
print(" ".join(map(str, row)))
Java 代码
import java.util.*;
public class Main {
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean rowZero = false, colZero = false;
// 记录第一行和第一列是否含有零
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) colZero = true;
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) rowZero = true;
}
// 使用第一行和第一列记录需要清零的行和列
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 依据第一行和第一列的标记进行清零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 处理第一行
if (rowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// 处理第一列
if (colZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
Main main = new Main();
Solution solution = main.new Solution();
solution.setZeroes(matrix);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
scanner.close();
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool rowZero = false, colZero = false;
// 记录第一行和第一列是否含有零
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) colZero = true;
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) rowZero = true;
}
// 使用第一行和第一列记录需要清零的行和列
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 依据第一行和第一列的标记进行清零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 处理第一行
if (rowZero) fill(matrix[0].begin(), matrix[0].end(), 0);
// 处理第一列
if (colZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> matrix[i][j];
Solution().setZeroes(matrix);
for (const auto& row : matrix) {
for (int num : row) cout << num << " ";
cout << endl;
}
return 0;
}