Monday, November 24, 2014

[LeetCode] 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.
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?

思路:

这题题意不是很清楚。很容易让人觉得置0是“连锁反应”,造成最后每个元素都为0。而实际题目的意思是,只有在原始矩阵中为0的数字才能将相应行列置0。而原本非0的数字,即使由于同行或同列的0元素而被置0了,也不能将它相关的行列置0。即这种置0的操作没有传递性,

1. O(mn)解法:克隆原来的matrix,然后扫描原来的matrix,遇到0,则在克隆版本中将对应的行列置0。
2. O(m+n)解法:用两个bool数组O(n)和O(m),分别记录每行和每列的是否需要被置0。最后根据这两个数组来置0整个矩阵。
3. O(1)解法:用第0行和第0列来记录第1 ~ m-1行和第1 ~ n-1列是否需要置0。而用两个变量记录第0行和第0列是否需要置0。

O(1)解法如下:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        if(matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        
        // find if the 1st row/col needs to be set as zero
        bool isFirstRowZero = false;
        bool isFirstColZero = false;
        for(int j=0; j<n; j++) {
            if(matrix[0][j]==0) {
                isFirstRowZero = true;
                break;
            }
        }
        for(int i=0; i<m; i++) {
            if(matrix[i][0]==0) {
                isFirstColZero = true;
                break;
            }
        }
        
        // use 1st row/col to record whether to set each col/row as zero
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                if(matrix[i][j]==0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        
        // set rows & cols
        for(int i=1; i<m; i++) {
            if(matrix[i][0]==0) setRowCol(matrix, i, true);
        }
        for(int j=1; j<n; j++) {
            if(matrix[0][j]==0) setRowCol(matrix, j, false);
        }
        
        // set first row & col
        if(isFirstRowZero) setRowCol(matrix, 0, true);
        if(isFirstColZero) setRowCol(matrix, 0, false);
    }
    
    void setRowCol(vector<vector<int>> &matrix, int index, bool isSetRow) {
        if(matrix.empty() || matrix[0].empty() || index<0) return;
        int m = matrix.size(), n = matrix[0].size();
        if((isSetRow && index>=m) || (!isSetRow && index>=n)) return;
        
        if(isSetRow) {
            for(int j=0; j<n; j++)
                matrix[index][j] = 0;
        }
        else {
            for(int i=0; i<m; i++)
                matrix[i][index] = 0;
        }
    }
};

6 comments:

  1. 如果第一行不用设 0, 用这行来记录每列, 那第一行数据不是丢了吗 ?

    ReplyDelete
    Replies
    1. 我是找到第一个 ij 为零, 用 i 行, j 列来记录

      Delete
    2. 不会丢失的,如果matrix[i][j]==0, 那么根据题目要求matrix[i][0]跟matrix[0][j] 肯定是要置零的,只不过是提前了而已。

      Delete
  2. O(m*n)的解法中,在do it in place的要求下,是不是應該掃描克隆的,改原本的。

    ReplyDelete