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;
    }
};

總結(jié)

1、自己的解法稍有討巧罢杉，臉滾鍵盤出了一個(gè)不會出現(xiàn)在測試樣例中的short類型變量orphon肥缔，遍歷矩陣谢揪，若出現(xiàn)0，則將出現(xiàn)0的那一行和那一列的非零元素改為orphon；第二次遍歷矩陣谢澈，將所有orphon的值改為0。
2御板、網(wǎng)上普遍流行的解法是找一個(gè)0位置锥忿，標(biāo)記其行row和列col，遍歷除去col行和col列的元素稳吮，如有0缎谷，則將row行和col列對應(yīng)的元素置0，再次遍歷除去col行和col列的元素灶似，如對應(yīng)row行和col列對應(yīng)的元素為0列林，則該位置置0，最后將（row酪惭，col）所在行和列元素全部置0