題目描述

給定一個 m x n 的矩陣，如果一個元素為 0 ，則將其所在行和列的所有元素都設為 0 。請使用 原地 算法。

題目分析

1. 題目中要求使用原地算法：即直接在輸入矩陣上進行修改。因此如果在輸入矩陣上把行/列的值修改成0后，在接下來的遍歷中就無法辨別矩陣中的0是原數值還是我們修改的0；
2. 因此我們需要使用兩個標記數組來記錄每一行和每一列是否有零出現；
3. 我們首先遍歷該矩陣數組一次，如果某個元素為 0，那么就將該元素所在的行和列所對應標記數組的位置置為 true；
4. 然后我們再次遍歷該數組，根據標記數組中的值來判斷是否需要更新原數組中的值。

Code

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<bool> row(m),col(n);for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (!matrix[i][j]) {row[i] = col[j] = true;}}}for (int i = 0; i< m; ++i) {for (int j = 0; j < n; ++j) {if (row[i] || col[j]) {matrix[i][j] = 0;}}}}
};