[LeetCode] Set Matrix Zeroes

更新时间：2021-12-25 18:46:22

This problem can be solved easily if we are allowed to use more than O(1) space. For example, you may create a copy of the original matrix (O(mn)-space) or just record the row and column indexes (O(m + n)-space). Well, is there a O(1)-space solution? Yes, you may refer to this link :-)

The key idea is to record the rows and columns that need to be set to zeroes directly in the matrix ( if (!matrix[i][j]) matrix[i][0] = matrix[0][j] = 0; ). The code is rewritten as follows.

 1 class Solution {
 2 public:
 3     void setZeroes(vector<vector<int>>& matrix) {
 4         int m = matrix.size(), n = matrix[0].size();
 5         bool c0 = false;
 6         for (int i = 0; i < m; i++) {
 7             if (!matrix[i][0]) c0 = true;
 8             for (int j = 1; j < n; j++)
 9                 if (!matrix[i][j]) matrix[i][0] = matrix[0][j] = 0;
10         }
11         for (int i = m - 1; i >= 0; i--) {
12             for (int j = n - 1; j; j--)
13                 if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
14             if (c0) matrix[i][0] = 0;
15         }
16     }
17 };

上一篇 : ：[LeetCode] Palindrome Number下一篇 : [LeetCode] Add Two Numbers

[LeetCode] Set Matrix Zeroes

相关阅读

推荐文章