題目

給定一個?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]]

分析

標記法

先判斷第一行和第一列是否包含 0，因為這兩部分既是數(shù)據(jù)又充當標記作用。

遍歷除第一行、第一列之外的所有元素。如果發(fā)現(xiàn)元素為 0，則將對應行的第一列和對應列的第一行設為 0，作為該行或該列需要清零的標記。

根據(jù)第一行和第一列的標記，將相應的元素置為 0。這里需要跳過第一行和第一列，因為它們需要后續(xù)單獨處理。

根據(jù)最初的檢查結(jié)果，將第一行或第一列全部置為 0。

時間復雜度：O()

空間復雜度：O(1)

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {if(matrix.empty() || matrix[0].empty()) return;int m = matrix.size(), n = matrix[0].size();bool firstRowZero = false, firstColZero = false;// 檢查第一行是否有 0for (int j = 0; j < n; ++j) {if (matrix[0][j] == 0) {firstRowZero = true;break;}}// 檢查第一列是否有 0for (int i = 0; i < m; ++i) {if (matrix[i][0] == 0) {firstColZero = true;break;}}// 用第一行和第一列記錄每一行和每一列是否需要置 0for (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; // 標記該列}}}// 根據(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;}}}// 若第一行原本存在 0，則將第一行全部置 0if (firstRowZero) {for (int j = 0; j < n; ++j) {matrix[0][j] = 0;}}// 若第一列原本存在 0，則將第一列全部置 0if (firstColZero) {for (int i = 0; i < m; ++i) {matrix[i][0] = 0;}}}
};