[LeetCode] 73. Set Matrix Zeroes

轉自LeetCode

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?

<Solution>

這題的題意是說，如果 matrix[i][j] = 0，則 row i 和 col j 上的值都要變成 0

例如

0 1 1 0    0 0 0 0
2 0 2 2 => 0 0 0 0
3 3 3 3    0 0 3 0

那題目也有要求，要 in place，且是不是可以不用到額外的空間

想法如下

• 使用 first row 和 first col 來記錄之後會變成 0 的 row 和 col。舉例

1 1 1 1
2 2 0 2 => matrix[1][2] = 0，這時候先將 matrix[0][2] 和 matrix[1][0] 都設為 0
3 3 3 3

1 1 0 1
0 2 0 2 => 這樣之後只要檢查 first row 和 first col，就會知道該 row 和該 col 是否要變為 0
3 3 3 3

• 因為把 first row 和 first col 拿來記錄用，所以要先檢查 first row 和 first col 本身需不需要全部變為 0

code 如下