【LeetCode热题100】73. 矩阵置零（矩阵）

一.题目要求

给定一个 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]]

提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
$2^{31}$ <= matrix[i][j] <= $2^{31} - 1$

进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

四.解题思路

没什么可说的官方解法是优化后的
在这里插入图片描述

五.代码实现

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        set<int> zeroh,zerol;
        vector<vector<int>>::iterator it;
        vector<int>::iterator itt;
        for (it = matrix.begin(); it != matrix.end(); it++)
        {
            for (itt = (*it).begin(); itt != (*it).end(); itt++)
            {
                if (*itt == 0)
                {
                    zeroh.insert(it - matrix.begin());
                    zerol.insert(itt - (*it).begin());
                }
            }
        }
        for (set<int>::iterator it = zeroh.begin(); it != zeroh.end(); it++)
        {
            for (vector<int>::iterator itl = matrix[*it].begin(); itl != matrix[*it].end(); itl++)
            {
                *itl = 0;
            }
        }

        for (set<int>::iterator it = zerol.begin(); it != zerol.end(); it++)
        {
            for (vector<vector<int>>::iterator ith = matrix.begin(); ith != matrix.end(); ith++)
            {
                (*ith)[*it] = 0;
            }
        }
    }
};

官方给的优化方法

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool firstRowZero = false, firstColZero = false;
        int rows = matrix.size(), cols = matrix[0].size();

        // Determine if the first row or first column is all zeros
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Use first row and column as markers, set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Zero out cells based on the first row and column
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Zero out the first row and column if needed
        if (firstColZero) {
            for (int i = 0; i < rows; i++) matrix[i][0] = 0;
        }
        if (firstRowZero) {
            for (int j = 0; j < cols; j++) matrix[0][j] = 0;
        }
    }
};