0 题目来源

力扣《程序员面试金典》

1 涉及到的知识点

矩阵、数组、set的使用

set：

C++中的一种STL，是一种集合，可以不重复地存放数据，插入数据后，在set内部会自动递增排序。
需要：
#include<set>
声明set（int类型）：
set<int> s;
set插入数据（如果插入set内已有的数据，则无效）：
s.insert(num);
使用迭代器遍历set：

for(set<int>::iterator it=c.begin();it!=c.end();it++)
{
    cout<<*it;//注意：使用迭代器时，迭代的某一项要加*号
}

vector<vector<int>>vec不符合C++98标准，需要这样：vector<vector<int> >vec

特殊思路

使用矩阵本身来记录信息，节省空间

2 题目描述

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

3 样例

示例 1：
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2：
输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

4 思路

方法一：使用set记录行列为零的情况

可以设置两个set，分别在遍历矩阵的过程中记录行列为零的情况。行set为r，记录需要设为零的行序号，列set为c，记录需要设为零的列序号。
记录完成后，遍历两个set，将相应行和列设为0。

方法二：使用矩阵本身记录行列为零的情况

为了减少空间复杂度，可以使用矩阵的第一行和第一列来记录每行每列为零的情况，然后另外使用一个变量记录第一行为零的情况，使用矩阵的[0][0]元素记录第一列为零的情况。
——本思路来自力扣官方题解

5 代码

方法一

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> r,c;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[i].size();j++)
            {
                if(matrix[i][j]==0)
                {
                    r.insert(i);
                    c.insert(j);
                }
            }
        }
        for(set<int>::iterator it=r.begin();it!=r.end();it++)
            for(int i=0;i<matrix[*it].size();i++)
                matrix[*it][i]=0;
        for(set<int>::iterator it=c.begin();it!=c.end();it++)
            for(int i=0;i<matrix.size();i++)
                matrix[i][*it]=0;
    }
};

方法二

来自力扣官方题解

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