【每日刷题】矩阵置零_给定一个mn的矩阵 如果一个元素为0

day12, 矩阵置零

题目来源：leetcode
给定一个 mxn 的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。请使用原地算法。

示例 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]
]

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

解答：空间换时间、遍历这两种方法上述已经提及，这里给出一个常数空间的解决方案：
我们可以设定一个标记值，对于某个位置上为0的元素，将其所在的列、行元素（除0之外）都转化为标记值，最后把该标记值转化为0即可。
问题是，标记值如何选取？首先要明确，标记值不能为0。其次，标记值不能等于矩阵内的任何一个元素。
刚开始我想到的办法是找到矩阵中的最大元素/最小元素，之后标记值设置为最大元素+1/最小元素-1，但是在测试用例中出现了 -2^31 和 2^31-1 两个数，因此该方法不能用。之后我开始暴力枚举找标记值，首先令标记值 min = -2^31 之后逐个去试，如果该标记不在矩阵中出现，则用该标记，否则标记++.

代码：

class Solution {
   
public:
    void setZeroes(vector<vector<int>>& matrix) {
   
        int min = -2147483648;
        while(1){
   
            
1
2
3
4
5
6
7
8