SetMatrixZeroes [source code]

public class SetMatrixZeroes {
static
/******************************************************************************/
class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return;
        int R = matrix.length, C = matrix[0].length;
        boolean col_0 = false;
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
            if (j == 0 && matrix[i][j] == 0) {
                col_0 = true;
                continue;
            }
            if (matrix[i][j] == 0)
                matrix[0][j] = matrix[i][0] = 0;
        }
        for (int i = R - 1; i >= 0; i--) for (int j = C - 1; j >= 1; j--) {
            if (matrix[0][j] == 0 || matrix[i][0] == 0)
                matrix[i][j] = 0;
        }
        if (col_0) {
            for (int i = 0; i < R; i++)
                matrix[i][0] = 0;
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SetMatrixZeroes.Solution tester = new SetMatrixZeroes.Solution();
        int[][][] inputs = {
            {{1,0}}, {{0, 0}},
            {{1,0,3}}, {{0,0,0}},
            {
                {1,2,3},
                {4,0,6},
                {7,8,9},
            }, {
                {1,0,3},
                {0,0,0},
                {7,0,9},
            },
            {{-1}, {2}, {3}}, {{-1}, {2}, {3}}, 
            {{-4,-2147483648,6,-7,0},{-8,6,-8,-6,0},{2147483647,2,-9,-6,-10}}, {{0,0,0,0,0},{0,0,0,0,0},{2147483647,2,-9,-6,0}},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[][] matrix = inputs[2 * i];
            String input_str = Matrix.printMatrix (matrix), ans_str = Matrix.printMatrix (inputs[2 * i + 1]);
            System.out.println (Printer.separator ());
            tester.setZeroes (matrix);
            String output_str = Matrix.printMatrix (matrix);
            System.out.printf ("%s -> \n%s, expected: \n%s", 
                input_str, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

没有例子的题目不代表例子不重要, 自己想例子;

不对啊, 这个就是CandyCrush那道题目的时候的crush那一步? 好像还简单一些; 那么其实用的就是intermediate state as flag的技巧;

难怪CandyCrush那道题的时候好多人都会做这个技巧了;

Follow-Up里面说的O(M+N)的做法思路很简单, 记录所有的0出现的row和col的index, 然后全部最后走一遍归0就行了; 或者说, 对没一个row或者col, 都记录一个flag: contains_zero;

另外这题也提示你, 空间开销虽然现在不如以前那么紧张了, 但是有些时候并不是说相比于时间cost就是完全可以忽略的; 设计算法的时候还是一个需要考虑的点;

简单的分析, 感觉如果用这个intermediate flag的做法, 可能会最后稍微增加时间开销: 一个pass可能走不完;

但是笔算了一下, 想了一下, 这里你脑子里不能光是想着for each cell这样的操作, 而是要具体分析你这个二重循环的顺序(row从上到下, 然后里面从左到右);

在这个顺序下面, 每一个cell被使用的顺序是:

这也是为什么只有向上的时候才能清零, 而向左的时候不能清零; 另外, 最后一行的处理, 一个比较简单的方法是最后单独给最后一个row一个扫, 然后清零; 当然也可以在原来的循环里面加一点代码, 直接在过程当中判断掉;

首先, 当你碰到一个0的时候, 你干什么? 直接重新立刻再走一遍所在的row和col吗? 需要走那么远吗? 事实上, 只要你知道自己的左边和上边邻居的状态, 你就知道你当前的位置是否应该是0了; 也就是说, 比如你在[1][1]看到一个0, 那么对于[1][3]的操作不用在[1][1]的iteration完成, 而是只要让[1][3]看到[1][2] <= 0就行了;

另外, 最后那个单独的, 用来清负数的pass能不能被合并掉? When is it safe to clear out the intermediate flags? 同样的, 看这个顺序, 是不是让你联想到类似DP填表的时候的顺序? 这里的dependency order就是向左和向上, 所以每一个cell可以立刻清掉自己左边和上边的parent, 因为他们的信息已经被自己包含了;

注意一下收尾问题: 如果已经走到最后一个row/col, 那么就直接zero而不是negate, 反正也没人需要用了;

负数被break掉了; 这个时候的代码是:

class Solution {  
    public void setZeroes(int[][] matrix) {  
        if (matrix.length == 0 || matrix[0].length == 0)  
            return;  
        int R = matrix.length, C = matrix[0].length;  
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {  
            if (i > 0 && matrix[i - 1][j] <= 0) {  
                if (matrix[i - 1][j] == 0)  
                    matrix[i][j] = 0;  
                else  
                    matrix[i - 1][j] = 0;  
            } else if (j > 0 && matrix[i][j - 1] <= 0) {  
                matrix[i][j] = i == R - 1 ? 0 : -matrix[i][j];  
            } else {  
                if (matrix[i][j] == 0) {  
                    for (int k = 0; k < i; k++)  
                        matrix[k][j] = 0;  
                    for (int k = 0; k < j; k++)  
                        matrix[i][k] = i == R - 1 ? 0 : -matrix[i][k];  
                }  
            }  
        }  
    }  
}

这个题目这样搞就很恶心人了; 想要用mod的方法来做InPlace flag, 但是感觉mod是不是更容易被break掉啊; 而且要mod肯定要算最值, 所以最后要先专门走一个专门的pass找到最大值和最小值;

不过讲道理, 这个也不能怪题目, LeetCode的题目还是很严禁的, 没说不包含负数就是没说, 这种事情面试的时候就是要自己开口问;

算了, 不写了, 这个题目最后花了很多时间, 做了很多思考, 最后其实也是没有办法了;

突然想到一个恶心的办法, 用bit flag来做? 这样实际上就只用了两个int, 但是这里没有说过dimension, 所以这个方案其实还是很容易被break掉的;

最后是模仿discussion做出来的一个解法, 速度是2ms (85%). 注意后面clear的时候, 第一行要最后clear;

没有editorial;

@mzchen said in Any shorter O(1) space solution?:

My idea is simple: store states of each row in the first of that row, and store states of each column in the first of that column. Because the state of row0 and the state of column0 would occupy the same cell, I let it be the state of row0, and use another variable "col0" for column0. In the first phase, use matrix elements to set states in a top-down way. In the second phase, use states to set matrix elements in a bottom-up way.

    void setZeroes(vector<vector<int> > &matrix) {  
        int col0 = 1, rows = matrix.size(), cols = matrix[0].size();  

        for (int i = 0; i < rows; i++) {  
            if (matrix[i][0] == 0) col0 = 0;  
            for (int j = 1; j < cols; j++)  
                if (matrix[i][j] == 0)  
                    matrix[i][0] = matrix[0][j] = 0;  
        }  

        for (int i = rows - 1; i >= 0; i--) {  
            for (int j = cols - 1; j >= 1; j--)  
                if (matrix[i][0] == 0 || matrix[0][j] == 0)  
                    matrix[i][j] = 0;  
            if (col0 == 0) matrix[i][0] = 0;  
        }  
    }

看来这个题目我是完全走错方向了, 联想错了类似问题最后导致整个思路都是错的; 事实上这题与其说使用的是InPlace flag, 实际上使用的是InPlace counts/semiring, 这个好像上次什么题目的时候见过一次, 只是稍微有点印象, 这里没有想起来; 反正这个技巧以后也要记住, 是O(1)space的一个套路之一;

第二个pass倒序本来是没有看懂:

@mzchen said in Any shorter O(1) space solution?:

@frk24
The first row should go last. It doesn't matter for the rest rows but for aesthetic reason it should be bottom-up.

所以其实理解了这个InPlace counts的技巧, 这个题目其实其他地方基本就没有难度了; 这个题目就考这一个点;

而且其实这个semiring的方法是有hint的, 你看他的Follow-Up的组织方式: 提到O(M+N)这个方式并不是单纯的告诉你, 这个是误区, 而是让你在这个基础上能不能再进一步;

@shotaemailgmail.com said in Any shorter O(1) space solution?:

I don't think there is need to do bottom-up in the 2nd phase. you can still do top-down and just skip the first row/column.

@lz2343 said in My AC java O(1) solution (easy to read):

public class Solution {  
    public void setZeroes(int[][] matrix) {  
        boolean fr = false,fc = false;  
        for(int i = 0; i < matrix.length; i++) {  
            for(int j = 0; j < matrix[0].length; j++) {  
                if(matrix[i][j] == 0) {  
                    if(i == 0) fr = true;  
                    if(j == 0) fc = true;  
                    matrix[0][j] = 0;  
                    matrix[i][0] = 0;  
                }  
            }  
        }  
        for(int i = 1; i < matrix.length; i++) {  
            for(int j = 1; j < matrix[0].length; j++) {  
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {  
                    matrix[i][j] = 0;  
                }  
            }  
        }  
        if(fr) {  
            for(int j = 0; j < matrix[0].length; j++) {  
                matrix[0][j] = 0;  
            }  
        }  
        if(fc) {  
            for(int i = 0; i < matrix.length; i++) {  
                matrix[i][0] = 0;  
            }  
        }  
    }  
}

@jaqenhgar said in My AC java O(1) solution (easy to read):

Explanation

    // fr = first row  
    // fc = first col  

    // Use first row and first column as markers.   
    // if matrix[i][j] = 0, mark respected row and col marker = 0; indicating  
       that later this respective row and col must be marked 0;  
    // And because you are altering first row and collumn,   
       you need to  have two variables to track their own status.   
    // So, for ex, if any one of the first row is 0, fr = 0,   
       and at the end set all first row to 0;  

所以其实还是一样的;

@lugiavn said in My C++ O(1) yoooooo:

I find the last row which has 0, and use it to store the 0-collumns.
Then go row by row set them to 0.
Then go column by column set them to 0.
Finally set the last row which has 0. It's long but hey it's O(1)

class Solution {  
public:  
    void setZeroes(vector<vector<int> > &matrix) {  

        int H = matrix.size();  
        int W = matrix[0].size();  

        // find the last 0 row  
        int last_0_row = -1;  
        for (int y = H - 1; y >= 0 && last_0_row == -1; y--)  
            for (int x = 0; x < W; x++)  
                if (matrix[y][x] == 0)  
                {  
                    last_0_row = y;  
                    break;  
                }  
        if (last_0_row == -1)  
            return;  

        // go row by row  
        for (int y = 0; y < last_0_row; y++)  
        {  
            bool this_is_a_0_row = false;  

            for (int x = 0; x < W; x++)  
            {  
                if (matrix[y][x] == 0)  
                {  
                    this_is_a_0_row = true;  
                    matrix[last_0_row][x] = 0;  
                }  
            }  

            if (this_is_a_0_row)  
            for (int x = 0; x < W; x++)  
            {  
                matrix[y][x] = 0;  
            }  
        }  

        // set collums to 0  
        for (int y = 0; y < H; y++)  
        for (int x = 0; x < W; x++)  
        {  
            if (matrix[last_0_row][x] == 0)  
                matrix[y][x] = 0;  
        }  

        // set the last 0 row   
        for (int x = 0; x < W; x++)  
        {  
            matrix[last_0_row][x] = 0;  
        }  
    }  
};

大概思路是类似的, 不过这个人观察到了另外一个事情, 事实上, 我们只需要row_counts和col_counts两者当中的一个就行了, 另一个可以在iterate的时候直接当时就clear掉; 因为row的循环比较容易, 所以就不记录row_counts, 在走这个row的时候, 顺便一个semiring记录是否有0, 有就当时回头立刻直接全部clear掉; 反正这个算法不可能有1pass了, 干脆就直接当时重新再走就行了;

又有点想思考1pass的做法了, 想了半天好像并找不到完全意义上的1pass, 而且其实我之前那个InPlace flag的时候的1pass, 最后的array access数量并没有减少: 你如果在一个cell要不停的看parent, 最后实际上跟单独走两个pass的循环又有什么区别呢?

@allen231x said in 21 lines concise and easy understand C++ solution, O(1) space, three steps:

class Solution {  
public:  
    void setZeroes(vector<vector<int>>& matrix) {  
        bool row = false, col = false;  
        for(int i = 0; i < matrix.size(); i++){  
            for(int j = 0; j < matrix[0].size(); j++){  
                if(matrix[i][j] == 0) {  
                    if(i == 0) row = true;  
                    if(j == 0) col = true;  
                    matrix[0][j] = matrix[i][0] = 0;  
                }  
            }  
        }  
        for(int i = 1; i < matrix.size(); i++){  
            for(int j = 1; j < matrix[0].size(); j++){  
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;  
            }  
        }  
        if(col){  
            for(int i = 0; i < matrix.size(); i++) matrix[i][0] = 0;  
        }  
        if(row){  
            for(int j = 0; j < matrix[0].size(); j++) matrix[0][j] = 0;  
        }  
    }  
};

没有太大区别;

submission基本波动;

class Solution {  
    public void setZeroes(int[][] matrix) {  
        boolean firstRowZero = false;  
        boolean firstColZero = false;  
        int rows = matrix.length;  
        int cols = matrix[0].length;  
        //check frist row  
        for(int i = 0; i < cols; ++i){  
            if(matrix[0][i] == 0){  
                firstRowZero = true;  
                break;  
            }  
        }  
        //check first col  
        for(int i = 0; i < rows; ++i){  
            if(matrix[i][0] == 0){  
                firstColZero = true;  
                break;  
            }  
        }  

        //set bit  
        for(int r = 1; r < rows; ++r){  
            for(int c = 1; c < cols; ++c){  
                if(matrix[r][c] == 0){  
                    matrix[r][0] = 0;  
                    matrix[0][c] = 0;  
                }  
            }  
        }  

        //set rows to zero  
        for(int i = 1; i < rows; ++i){  
            if(matrix[i][0] == 0){  
                for(int j = 0; j < cols; ++j){  
                    matrix[i][j] = 0;  
                }  
            }  
        }  

        //set cols to zero  
        for(int i = 1; i < cols; ++i){  
            if(matrix[0][i] == 0){  
                for(int j = 0; j < rows; ++j){  
                    matrix[j][i] = 0;  
                }  
            }  
        }  

        //set first row to zero  
        if(firstRowZero){  
            for(int j = 0; j < cols; ++j){  
                matrix[0][j] = 0;  
            }  
        }  

        //set first col to zero  
        if(firstColZero){  
            for(int j = 0; j < rows; ++j){  
                matrix[j][0] = 0;  
            }  
        }  

    }  
}

干脆也加一个row_0的思路, 说实话, 这样感觉是干净一些;

Problem Description

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?

Difficulty:Medium
Total Accepted:129.3K
Total Submissions:355.1K
Contributor:LeetCode
Companies
microsoftamazon
Related Topics
array
Similar Questions
Game of Life