0073. 矩陣置零 · ttttt

# 0073. 矩陣置零 ## 題目地址(73. 矩陣置零) <https://leetcode-cn.com/problems/set-matrix-zeroes/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個 m x n 的矩陣，如果一個元素為 0，則將其所在行和列的所有元素都設為 0。請使用原地算法。示例 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] ] 進階: 一個直接的解決方案是使用 O(mn) 的額外空間，但這并不是一個好的解決方案。一個簡單的改進方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。你能想出一個常數空間的解決方案嗎？ ``` ``` ## 前置知識 - 狀態壓縮 ## 公司 - 阿里 - 百度 - 字節 ## 思路符合直覺的想法是，使用一個 m + n 的數組來表示每一行每一列是否”全部是 0“，先遍歷一遍去構建這樣的 m + n 數組，然后根據這個 m + n 數組去修改 matrix 即可。 ![](https://img.kancloud.cn/00/a3/00a3a8ba77d6553d3a2e7aebc77696a2_604x437.jpg) 這樣的時間復雜度 O(m \* n), 空間復雜度 O(m + n). 代碼如下： ``` <pre class="calibre18">``` var setZeroes = function (matrix) { if (matrix.length === 0) return matrix; const m = matrix.length; const n = matrix[0].length; const zeroes = Array(m + n).fill(false); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const item = matrix[i][j]; if (item === 0) { zeroes[i] = true; zeroes[m + j] = true; } } } for (let i = 0; i < m; i++) { if (zeroes[i]) { matrix[i] = Array(n).fill(0); } } for (let i = 0; i < n; i++) { if (zeroes[m + i]) { for (let j = 0; j < m; j++) { matrix[j][i] = 0; } } } return matrix; }; ``` ``` 但是這道題目還有一個 follow up，要求使用 O(1)的時間復雜度。因此上述的方法就不行了。但是我們要怎么去存取這些信息（哪一行哪一列應該全部為 0）呢？一種思路是使用第一行第一列的數據來代替上述的 zeros 數組。這樣我們就不必借助額外的存儲空間，空間復雜度自然就是 O(1)了。由于我們不能先操作第一行和第一列，因此我們需要記錄下”第一行和第一列是否全是 0“這樣的一個數據，最后根據這個信息去修改第一行和第一列。具體步驟如下： - 記錄下”第一行和第一列是否全是 0“這樣的一個數據 - 遍歷除了第一行和第一列之外的所有的數據，如果是 0，那就更新第一行第一列中對應的元素為 0> 你可以把第一行第一列看成我們上面那種解法使用的 m + n 數組。 - 根據第一行第一列的數據，更新 matrix - 最后根據我們最開始記錄的”第一行和第一列是否全是 0“去更新第一行和第一列即可 ![](https://img.kancloud.cn/2b/14/2b1474c18d101d3d1824c790f0a7be1e_730x321.jpg) ## 關鍵點 - 使用第一行和第一列來替代我們 m + n 數組 - 先記錄下”第一行和第一列是否全是 0“這樣的一個數據，否則會因為后續對第一行第一列的更新造成數據丟失 - 最后更新第一行第一列 ## 代碼 - 語言支持：JS，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=73 lang=javascript * * [73] Set Matrix Zeroes */ /** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var setZeroes = function (matrix) { if (matrix.length === 0) return matrix; const m = matrix.length; const n = matrix[0].length; // 時間復雜度 O(m * n), 空間復雜度 O(1) let firstRow = false; // 第一行是否應該全部為0 let firstCol = false; // 第一列是否應該全部為0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const item = matrix[i][j]; if (item === 0) { if (i === 0) { firstRow = true; } if (j === 0) { firstCol = true; } matrix[0][j] = 0; matrix[i][0] = 0; } } } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { const item = matrix[i][j]; if (matrix[0][j] == 0 || matrix[i][0] == 0) { matrix[i][j] = 0; } } } // 最后處理第一行和第一列 if (firstRow) { for (let i = 0; i < n; i++) { matrix[0][i] = 0; } } if (firstCol) { for (let i = 0; i < m; i++) { matrix[i][0] = 0; } } return matrix; }; ``` ``` Python3 Code: 直接修改第一行和第一列為 0 的解法： ``` <pre class="calibre18">``` class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ def setRowZeros(matrix: List[List[int]], i:int) -> None: C = len(matrix[0]) matrix[i] = [0] * C def setColZeros(matrix: List[List[int]], j:int) -> None: R = len(matrix) for i in range(R): matrix[i][j] = 0 isCol = False R = len(matrix) C = len(matrix[0]) for i in range(R): if matrix[i][0] == 0: isCol = True for j in range(1, C): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 for j in range(1, C): if matrix[0][j] == 0: setColZeros(matrix, j) for i in range(R): if matrix[i][0] == 0: setRowZeros(matrix, i) if isCol: setColZeros(matrix, 0) ``` ``` 另一種方法是用一個特殊符合標記需要改變的結果，只要這個特殊標記不在我們的題目數據范圍（0 和 1）即可，這里用 None。 ``` <pre class="calibre18">``` class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ 這題要解決的問題是，必須有個地方記錄判斷結果，但又不能影響下一步的判斷條件；直接改為0的話，會影響下一步的判斷條件；因此，有一種思路是先改為None，最后再將None改為0；從條件上看，如果可以將第一行、第二行作為記錄空間，那么，用None應該也不算違背題目條件； """ rows = len(matrix) cols = len(matrix[0]) # 遍歷矩陣，用None記錄要改的地方，注意如果是0則要保留，否則會影響下一步判斷 for r in range(rows): for c in range(cols): if matrix[r][c] is not None and matrix[r][c] == 0: # 改值 for i in range(rows): matrix[i][c] = None if matrix[i][c] != 0 else 0 for j in range(cols): matrix[r][j] = None if matrix[r][j] != 0 else 0 # 再次遍歷，將None改為0 for r in range(rows): for c in range(cols): if matrix[r][c] is None: matrix[r][c] = 0 ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(1)O(1)O(1) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) ## 擴展為什么選擇第一行第一列，選擇其他行和列可以么？為什么？