set matrix zero

set matrix zero

Think twice

This problem use time complexity at least O(n*n), because we need visit each element at least once. Also we could use an matrix to mark the result of this matrix and this may takes space complexity O(n*n). A better way to resolve this problem is get two vector mark rows and columns, whch takes space complexity O(n). The best way to resolve this problem is using constant space complexity. We use markr and c to mark whether the first row and the first column has zero. And we use first row and column to mark the matrix. Attention!After we mark the matrix, when we set zero of matrix, begin from the second row and second colum.

 1 class Solution {
 2 public:
 3     void setZeroes(vector<vector<int> > &matrix) {
 4         int r = 0;
 5         int c = 0;
 6         int n = matrix.size();
 7         if ( !n ) {
 8             return;
 9         }
10         int m = matrix[0].size();
11         if ( !m ) {
12             return;
13         }
14         for ( int i = 0; i < n; i++ ) {
15             if ( 0 == matrix[i][0] ) {
16                 c = 1;
17                 break;
18             }
19         }
20         for ( int i = 0; i < m; i++ ) {
21             if ( 0 == matrix[0][i] ) {
22                 r = 1;
23                 break;
24             }
25         }
26         for ( int i = 1; i < n; i++ ) {
27             for ( int j = 1; j < m; j++ ) {
28                 if ( 0 == matrix[i][j] ) {
29                     matrix[i][0] = 0;
30                     matrix[0][j] = 0;
31                 }
32             }
33         }
34         for ( int i = 1; i < n; i++ ) {
35             if ( 0 == matrix[i][0] ) {
36                 for ( int j = 0; j < m; j++ ) {
37                     matrix[i][j] = 0;
38                 }
39             }
40         }
41         for ( int j = 1; j < m; j++ ) {
42             if ( 0 == matrix[0][j] ) {
43                 for ( int i = 0; i < n; i++ ) {
44                     matrix[i][j] = 0;
45                 }
46             }
47         }
48         if ( 1 == c ) {
49             for ( int i = 0; i < n; i++ ) {
50                 matrix[i][0] = 0;
51             }
52         }
53         if ( 1 == r ) {
54             for ( int i = 0; i < m; i++ ) {
55                 matrix[0][i] = 0;
56             }
57         }
58     }
59 };

Loading Disqus comments...
Table of Contents