LeetCode73 Set Matrix Zeroes

题目：

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.（Medium）

分析：

题意很简单，就是把为0的元素所在的行和列都置0；

首先不能直接边循环边做，这样会造成很多本来不是0的元素被置0之后，在后续判断中将它的行列也置0；

所以简单的方法是建立两个数组，存行和列是否为0的情况，遍历一遍更新两个数组，再遍历一遍把应该置0的全部置0。

自己写的时候先考虑用了个set便于不记录重复的下标，所以有如下代码1：

 class Solution {

 public:

     void setZeroes(vector<vector<int>>& matrix) {

         set<int> rowflag;

         set<int> colomnflag;

         for (int i = ; i < matrix.size(); ++i) {

             for (int j = ; j < matrix[].size(); ++j) {

                 if (matrix[i][j] == ) {

                     rowflag.insert(i);

                     colomnflag.insert(j);

                 }

             }

         }

         for (auto i : rowflag) {

             for (int j = ; j < matrix[].size(); ++j) {

                 matrix[i][j] = ;

             }

         }

         for (auto i : colomnflag) {

             for (int j = ; j < matrix.size(); ++j) {

                 matrix[j][i] = ;

             }

         }

         return;

     }

 };

程序还算简洁，记录最坏情况那里空间复杂度是为的O(nlogn + mlogm)；

记录bool数组的方式，自己开始觉得写起来不够简洁。

后来看了讨论区大家的写法，发现第二次的用循环一遍，然后rowflag[i] || colonmnflag[j]可以很简洁的写出来，所以有如下代码2：

 class Solution {

 public:

     void setZeroes(vector<vector<int>>& matrix) {

         int rowflag[matrix.size()] = {};

         int colomnflag[matrix[].size()] = {};

         for (int i = ; i < matrix.size(); ++i) {

             for (int j = ; j < matrix[].size(); ++j) {

                 if (matrix[i][j] == ) {

                     rowflag[i] = ;

                     colomnflag[j] = ;

                 }

             }

         }

         for (int i = ; i < matrix.size(); ++i) {

             for (int j = ; j < matrix[].size(); ++j) {

                 if (rowflag[i] ==  || colomnflag[j] == ) {

                     matrix[i][j] = ;

                 }

             }

         }

         return;

     }

 };

题目的follow-up中问道能否用常数的空间解决该问题，做法就是用两个变量记录第一行和第一列是否有0，

然后用第一行和第一列充当rowflag,colomnflag即可。

巴特西

LeetCode73 Set Matrix Zeroes

最新文章

热门文章