###### tags: `Leetcode` `medium` `array` `python` `Top 100 Liked Questions`

# 73. Set Matrix Zeroes

## [題目連結:] https://leetcode.com/problems/set-matrix-zeroes/

## 題目:
Given an ```m x n``` integer ```matrix matrix```, if an element is ```0```, set its entire row and column to ```0```'s.

You must do it ```in place```.

**Follow up:**

* A straightforward 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?


#### [圖片來源:]https://leetcode.com/problems/set-matrix-zeroes/

## 解題想法:
* 題目要求檢查矩陣中，若某格為0，則將其整行、整列都改為0
* 要求in-place在原矩陣更改
* 要求space:O(1)

* 解法: **Space:O(1)** time:O(m * n * (m+n))
* 初始: 設兩個flag標記第一行、第一列是否出現0
* fm=1
* fn=1
* 若出現0，將其=0
* Step1:
* 遍歷第一行，查看是否出現0
* 若出現0，將**fm=0** then break(找到就可以了)
* 遍歷第一列，查看是否出現0
* 若出現0，將**fn=0** then break
* Step2:
* 遍歷矩陣剩下的位置，若有出現0，則將其行列的**第一個元素標0**
* Step3:
* 根據前面標記，找**第一列**中(不含原點(0,0))所有出現0的位置，將其所對應的**行**全部標成0
* 根據前面標記，找**第一行**中(不含原點(0,0))所有出現0的位置，將其所對應的**列**全部標成0
* Step4:
* 判斷第一行列整行的最終標記 (要最後判斷，不然先做的話，前面步驟執行不了)
* 若fm==0，第一行全為0
* 若fn==0，第一列全為0

* 示意圖:

ex: 
   t=1
t=1 0       1       2       0
    3       4       5       2
    1       3      '0'      5
                此出現0 所以將該行列的第一個元素標0
=>
    0       1      '0'       0
    3       4       5        2
   '0'      3      '0'       5

=>掃描第一列(從1開始):將其出現0的該行也全變0
    0       1      '0'      '0'
    3       4      '0'      '0'
    0       3      '0'      '0'

=>掃描第一行(從3開始):將其出現0的該列也全變0
    0       1       0       0
    3       4       0       0
   '0'     '0'     '0'     '0'

再由fm,fn更新第一行列所有值
#初始fm,fn=1   若fm,fn=0則表示原先第一行列就有出現0的跡象 全部填成0
    0       0       0       0
    0       4       0       0
    0       0       0       0

## Python: Space:O(1)

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        #space: O(1)  time: O(m*n*(m+n))
        #法1: 用兩格flag標記第一行列是否出現0
        m = len(matrix)
        n = len(matrix[0])
        fm = 1
        fn = 1

        #遍歷第一行 找是否有出現0:
        for i in range(m):
            if matrix[i][0]==0:
                fm = 0
                break
        #遍歷第一列 找是否有出現0:
        for j in range(n):
            if matrix[0][j]==0:
                fn = 0
                break
        #遍歷矩陣剩下的位置，如果有出現0，則將其該行列的第一個元素標0
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]==0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        #根據標記 找第一列中(除了原點外)出現0的位置
        #將其所對應的該行全部標成0
        for j in range(1,n):
            if matrix[0][j]==0:
                for i in range(1,m):
                    matrix[i][j] = 0
        #根據標記 找第一行中(除了原點外)出現0的位置
        #將其所對應的該列全部標成0
        for i in range(1,m):
            if matrix[i][0]==0:
                for j in range(1,n):
                    matrix[i][j] = 0
        #判斷第一行列生死
        if fm == 0:
            for i in range(m):
                matrix[i][0]=0
        if fn == 0:
            for j in range(n):
                matrix[0][j]=0


result = Solution()
matrix = [[1,1,1],[1,0,1],[1,1,1]]
ans = result.setZeroes(matrix)
print(matrix)