Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

Example 2:

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

Follow up:

• 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?

AC代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        short orphon = -283492;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] != 0) continue;
                for (int k = 0; k < matrix[0].size(); ++k) 
                    if (matrix[i][k] != 0) matrix[i][k] = orphon;                
                for (int k = 0; k < matrix.size(); ++k) 
                    if (matrix[k][j] != 0) matrix[k][j] = orphon;                
            }
        }
        for (int i = 0; i < matrix.size(); ++i) 
            for (int j = 0; j < matrix[0].size(); ++j) 
                if (matrix[i][j] == orphon) matrix[i][j] = 0;                    
    }
};

正常解法

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return;
        short row = -1, col = -1;
        bool f = false;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == 0) {
                    row = i;
                    col = j;
                    f = true;
                    break;
                }
            }
            if (f) break;
        }
        if (row == -1) return; //矩阵中没有0，直接返回
        for (int i = 0; i < matrix.size(); ++i) {
            if (i == row) continue;
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (j == col) continue;
                if (matrix[i][j] == 0) {
                    matrix[row][j] = 0;
                    matrix[i][col] = 0;
                }
            }
        }
        for (int i = 0; i < matrix.size(); ++i) {
            if (i == row) continue;
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (j == col) continue;
                if (matrix[i][col] == 0 || matrix[row][j] == 0)
                    matrix[i][j] = 0;
            }
        }
        for (int i = 0; i < matrix.size(); ++i) matrix[i][col] = 0;
        for (int j = 0; j < matrix[0].size(); ++j) matrix[row][j] = 0;
    }
};

总结

1、自己的解法稍有讨巧，脸滚键盘出了一个不会出现在测试样例中的short类型变量orphon，遍历矩阵，若出现0，则将出现0的那一行和那一列的非零元素改为orphon；第二次遍历矩阵，将所有orphon的值改为0。
2、网上普遍流行的解法是找一个0位置，标记其行row和列col，遍历除去col行和col列的元素，如有0，则将row行和col列对应的元素置0，再次遍历除去col行和col列的元素，如对应row行和col列对应的元素为0，则该位置置0，最后将（row，col）所在行和列元素全部置0