写作网站好吗百度服务热线

题目

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

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

C++代码

#include <iostream>
#include <vector>
using namespace std;/*
* 定义矩阵置零函数
* 使用两个标记变量flag_row0,flag_col0分别记录第一行和第一列是否原本包含0
* 其他行列元素如果为0，改变元素所在第一行第一列为0
* 反过来使用第一行与第一列去更新其他行与列
* 使用两个标记变量更新第一行与第一列
*/
void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();int flag_col0 = false, flag_row0 = false;for (int i = 0; i < m; ++i) {if (!matrix[i][0]) {flag_col0 = true;}}for (int j = 0; j < n; ++j) {if (!matrix[0][j]) {flag_row0 = true;}}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {if (!matrix[i][j]) {matrix[i][0] = matrix[0][j] = 0;}}}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {if (!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}for (int i = 0; i < m; ++i) {if (flag_col0) {matrix[i][0] = 0;}}for (int j = 0; j < n; ++j) {if (flag_row0) {matrix[0][j] = 0;}}
}
int main() {vector<vector<int>> matrix = { {0,1,2,0},{3,4,5,2},{1,3,1,5} };setZeroes(matrix);for (int i = 0; i < matrix.size(); ++i) {for (int j = 0; j < matrix[0].size(); ++j) {cout << matrix[i][j] << " ";}cout << endl;}return 0;
}

分析

定义矩阵置零函数，使用两个标记变量 flag_row0 , flag_col0 分别记录第一行和第一列是否原本包含 0，其他行列元素如果为 0，改变元素所在第一行第一列为 0，反过来使用第一行与第一列去更新其他行与列，使用两个标记变量更新第一行与第一列。