【LeetCode】 73. Set Matrix Zeroes

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:

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

給予一個 m x n 的矩陣，如果有一個元素為0，將和它同列、同行的都設成0。用原地演算法完成。

進階：

• 直接使用O(mn)空間複雜度的答案可能是個不好的想法。
• 一個簡單的進步是使用O(m + n)空間複雜度，但仍然有更好的答案。
• 你可以在常數空間複雜度中完成嗎？

Example:

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]
]

Solution

• 因為不能使用和m、n有關的新的記憶體空間，我們直接使用m[0][j]來標註哪些橫排要清空，m[i][0]來標註哪些直排要清空。
• m[0][0]沒辦法同時記錄是直排還是橫排要清空，因此要一個額外bool去存。

Code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool firstZero = false;
        for(int i = 0; i < matrix.size(); i++)
        {
            firstZero |= !matrix[i][0];
            for(int j = 1; j < matrix[0].size(); j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[0][j] = 0;
                    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(matrix[0][0] == 0)
            for(int j = 0; j < matrix[0].size(); j++)
                matrix[0][j] = 0;
        
        if(firstZero)
            for(int i = 0; i < matrix.size(); i++)
                matrix[i][0] = 0;
        
    }
};

tags: LeetCode C++