力扣算法题—073矩阵置零

╰+哭是因爲堅強的太久メ 2022-10-02 15:55 238阅读 0赞

给定一个 *m* x *n* 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用[原地][Link 1]算法。

示例 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(*m**n*) 的额外空间，但这并不是一个好的解决方案。
 *  一个简单的改进方案是使用 O(*m* + *n*) 的额外空间，但这仍然不是最好的解决方案。
 *  你能想出一个常数空间的解决方案吗？

1 #include "_000库函数.h"
     2 
     3 
     4 //先使用m*n的额外空间
     5 class Solution {
     6 public:
     7     void setZeroes(vector<vector<int>>& matrix) {
     8         vector<vector<int>>temp = matrix;
     9         for (int i = 0; i < matrix.size(); ++i)
    10             for (int j = 0; j < matrix[0].size(); ++j)
    11                 if (temp[i][j] == 0) {
    12                     for (int t = 0; t < matrix.size(); ++t)
    13                         matrix[t][j] = 0;
    14                     for (int t = 0; t < matrix[0].size(); ++t)
    15                         matrix[i][t] = 0;
    16                 }
    17     }
    18 };
    19 
    20 //使用m+n的额外空间，只需要记录的行和列就行
    21 //此处可以再优化一下，不另外开辟空间，使用原矩阵的第一行和第一列来记录就行
    22 class Solution {
    23 public:
    24     void setZeroes(vector<vector<int>>& matrix) {
    25         vector<int>r(matrix.size(), 0);//行标记  m
    26         vector<int>l(matrix[0].size(), 0);//列标记  n
    27         for (int i = 0; i < matrix.size(); ++i)
    28             for (int j = 0; j < matrix[0].size(); ++j)
    29                 if (matrix[i][j] == 0) {
    30                     r[i] = 1;
    31                     l[j] = 1;
    32                 }
    33 
    34         for (int i = 0; i < matrix.size(); ++i)
    35             if (r[i])
    36                 for (int j = 0; j < matrix[0].size(); ++j)
    37                     matrix[i][j] = 0;
    38 
    39         for (int j = 0; j < matrix[0].size(); ++j)
    40             if (l[j])
    41                 for (int i = 0; i < matrix.size(); ++i)
    42                     matrix[i][j] = 0;
    43     }
    44                     
    45 };
    46 void T073() {
    47     Solution s;
    48     vector<vector<int>>v;
    49     v = { {
        1,1,1}, {
        1,0,1},{
        1,1,1} };
    50     s.setZeroes(v);
    51     for (auto &a : v) {
    52         for (auto b : a)
    53             cout << b << "  ";
    54         cout << endl;
    55     }
    56     cout << endl;
    57     v = { {
        0,1,2,0}, {
        3,4,5,2},{
        1,3,1,5} };
    58     s.setZeroes(v);
    59     for (auto &a : v) {
    60         for (auto b : a)
    61             cout << b << "  ";
    62         cout << endl;
    63     }
    64     cout << endl;
    65 
    66 
    67 }

转载于:https://www.cnblogs.com/zzw1024/p/10705526.html

[Link 1]: http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95