LeetCode: Set Matrix Zeroes 解题报告

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.

click to show follow up.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

SOLUTION 1:

题目要求O(1)的空间消耗。

1. 我们可以使用第一行，第一列来作为Flag，记录某一行，某一列是否应该被设置为0.

2. 因为第一行，第一列共用左上角的flag，所以我们需要另外找2个flag来定义第一行，第一列本身是否应该设置为0.

row1Zero， col1Zero

3. 先扫描首行，首列把首行首列的flag算出。

4. 扫描其他的矩阵，将第一行每一列的flag算出。

5. 设置矩阵中除了首行首列的cells.

6. 设置首行，设置首列。

 1 public class Solution {
 2     public void setZeroes(int[][] matrix) {
 3         if (matrix == null || matrix.length == 0 
 4             || matrix[0].length == 0) {
 5             return;        
 6         }
 7         
 8         boolean row1Zero = false;
 9         boolean col1Zero = false;
10         
11         int rows = matrix.length;
12         int cols = matrix[0].length;
13         
14         // Determine if the first column should be Zero.
15         for (int i = 0; i < rows; i++) {
16             if (matrix[i][0] == 0) {
17                 col1Zero = true;
18                 break;
19             }
20         }
21         
22         // Determine if the first row should be Zero.
23         for (int i = 0; i < cols; i++) {
24             if (matrix[0][i] == 0) {
25                 row1Zero = true;
26                 break;
27             }
28         }
29         
30         // we use the first row and the first col as the flag to record the 
31         // cells whether or not set to 0.
32         for (int i = 1; i < rows; i++) {
33             for (int j = 1; j < cols; j++) {
34                 // 注意了，这个矩阵是0和非0，并不是0和1.
35                 if (matrix[i][j] == 0) {
36                     // set the flag in the first line and the first column                
37                     matrix[i][0] = 0;
38                     matrix[0][j] = 0;
39                 }
40             }
41         }
42         
43         // set the inner cells.
44         // Be careful: i, j start from 1.
45         for (int i = 1; i < rows; i++) {
46             for (int j = 1; j < cols; j++) {
47                 if (matrix[i][0] == 0
48                    || matrix[0][j] == 0) {
49                     matrix[i][j] = 0;   
50                 }
51             }
52         }
53         
54         // set the first row.
55         if (row1Zero) {
56             for (int i = 0; i < cols; i++) {
57                 matrix[0][i] = 0;
58             }    
59         }
60         
61         // set the first col.
62         if (col1Zero) {
63             for (int i = 0; i < rows; i++) {
64                 matrix[i][0] = 0;
65             }    
66         }
67         
68         return;
69     }
70 }

View Code

LeetCode: Set Matrix Zeroes 解题报告

相关推荐