73. 矩陣置零

題目描述

給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0，則將其所在行和列的所有元素都設(shè)為 0。請(qǐng)使用原地算法。

示例 1:

輸入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
輸出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:

輸入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
輸出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

進(jìn)階:

一個(gè)直接的解決方案是使用 O(mn) 的額外空間，但這并不是一個(gè)好的解決方案。
一個(gè)簡(jiǎn)單的改進(jìn)方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
你能想出一個(gè)常數(shù)空間的解決方案嗎？

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/set-matrix-zeroes

解題思路

• 方法1:額外存儲(chǔ)空間方法
  如果矩陣中任意一個(gè)格子有零我們就記錄下它的行號(hào)和列號(hào)，這些行和列的所有格子在下一輪中全部賦為零。
• 方法2:

1. 遍歷整個(gè)矩陣，如果 cell[i][j] == 0 就將第 i 行和第 j 列的第一個(gè)元素標(biāo)記。
2. 第一行和第一列的標(biāo)記是相同的，都是 cell[0][0]，所以需要一個(gè)額外的變量告知第一列是否被標(biāo)記，同時(shí)用 cell[0][0] 繼續(xù)表示第一行的標(biāo)記。
3. 然后，從第二行第二列的元素開(kāi)始遍歷，如果第 r 行或者第 c 列被標(biāo)記了，那么就將 cell[r][c] 設(shè)為 0。這里第一行和第一列的作用就相當(dāng)于方法一中的 row_set 和 column_set 。
4. 然后我們檢查是否 cell[0][0] == 0 ，如果是則賦值第一行的元素為零。
5. 然后檢查第一列是否被標(biāo)記，如果是則賦值第一列的元素為零。

代碼實(shí)現(xiàn)

• 方法1

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        R = len(matrix)
        C = len(matrix[0])
        rows, cols = set(), set()

        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        for i in range(R):
            for j in range(C):
                if i in rows or j in cols:
                    matrix[i][j] = 0

• 方法2:

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        is_col = False
        R = len(matrix)
        C = len(matrix[0])

        for i in range(R):
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        if is_col:
            for i in range(R):
                matrix[i][0] = 0