題目資訊

題目編號: 73
題目連結: Set Matrix Zeroes
主題: Array, Hash Table, Matrix

題目敘述

給定一個 $m \times n$ 的整數矩陣 $matrix$，如果一個元素是 $0$，則將其整行和整列都設為 $0$。

你必須原地完成這個操作。

範例 1:

Example 1

輸入: matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出: [[1,0,1],[0,0,0],[1,0,1]]

範例 2:

Example 2

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

約束:

$m == matrix.length$
$n == matrix[0].length$
$1 \leq m, n \leq 200$
$-2^{31} \leq matrix[i][j] \leq 2^{31} - 1$

進階:

使用 $O(mn)$ 空間的直接解決方案可能不是一個好的主意。
一個簡單的改進方案使用 $O(m + n)$ 空間，但仍然不是最佳解。
你能設計一個常數空間的解決方案嗎？

直覺

這個問題要求我們將某個元素為零的整個行和列設為零。挑戰在於需要原地進行操作，不能使用額外的空間，這意味著我們不能使用額外的陣列或列表來記錄哪些行和列需要被設為零。主要的洞察在於利用矩陣的第一行和第一列來儲存這些資訊，同時也要記錄第一行是否原本就包含零。這使得我們能夠在不使用額外空間的情況下確保所有需要被設為零的行和列皆被正確地處理。

解法

基於問題的限制和要求，最佳的解決方法是利用矩陣本身來減少空間複雜度。以下是此方法的步驟概述：

初始化：確定矩陣的大小，m 代表行數，n 代表列數。引入一個布林標誌 firstRowHasZero 用於檢查第一行是否最初包含任何零。
檢查第一行：遍歷第一行以檢查零。如果找到零，將 firstRowHasZero 設為 true。這一步驟有助於確保在其他操作完成後，我們可以正確地將第一行設為零（如果它最初包含零的話）。
標記行和列：從第二行（索引為 1）開始使用巢狀迴圈遍歷矩陣。如果在位置 $(i, j)$ 發現零，則將第 i 行和第 j 列的第一個元素標記為零。這用作指示器，表示整個第 i 行和第 j 列最終應被設為零。
設零行：設置標記後，再次從第二行開始遍歷行。如果行的第一個元素為零，則將該行的所有元素設為零。
設零列：同樣地，從第一列開始遍歷列。如果列的第一個元素為零，則將該列的所有元素設為零。
如有需要，更新第一行：最後，如果 firstRowHasZero 為真，則將整個第一行設為零，以考慮最初存在的零。

此方法透過直接對輸入矩陣進行修改，實現了利用恆定空間進行零標記過程的處理。此方法確保矩陣被原地更改，滿足問題的限制條件。

程式碼

C++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(); // 矩陣的行數
        int n = matrix[0].size(); // 矩陣的列數
        bool firstRowHasZero = false; // 標誌檢查第一行是否有任何零

        // 檢查第一行是否有任何零並相應地設置標誌
        for (int col = 0; col < n; ++col) {
            if (matrix[0][col] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // 使用第一行和第一列作為標記要歸零的行和列
        for (int row = 1; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                if (matrix[row][col] == 0) {
                    matrix[0][col] = 0; // 標記列
                    matrix[row][0] = 0; // 標記行
                }
            }
        }

        // 根據第一列中的標記將單元格歸零
        for (int row = 1; row < m; ++row) {
            if (matrix[row][0] == 0) {
                for (int col = 1; col < n; ++col) {
                    matrix[row][col] = 0;
                }
            }
        }

        // 根據第一行中的標記將單元格歸零
        for (int col = 0; col < n; ++col) {
            if (matrix[0][col] == 0) {
                for (int row = 1; row < m; ++row) {
                    matrix[row][col] = 0;
                }
            }
        }

        // 如果第一行最初有零，將整個第一行歸零
        if (firstRowHasZero) {
            for (int col = 0; col < n; ++col) {
                matrix[0][col] = 0;
            }
        }
    }
};

Python

class Solution:
    def setZeroes(self, matrix):
        m = len(matrix)  # 矩陣的行數
        n = len(matrix[0])  # 矩陣的列數
        firstRowHasZero = False  # 標誌檢查第一行是否有零

        # 檢查第一行是否有任何零並相應地設置標誌
        for col in range(n):
            if matrix[0][col] == 0:
                firstRowHasZero = True
                break

        # 使用第一行和第一列作為標記，用於標記需要置零的行和列
        for row in range(1, m):
            for col in range(n):
                if matrix[row][col] == 0:
                    matrix[0][col] = 0  # 標記列
                    matrix[row][0] = 0  # 標記行

        # 根據第一列中的標記將單元格置零
        for row in range(1, m):
            if matrix[row][0] == 0:
                for col in range(1, n):
                    matrix[row][col] = 0

        # 根據第一行中的標記將單元格置零
        for col in range(n):
            if matrix[0][col] == 0:
                for row in range(1, m):
                    matrix[row][col] = 0

        # 如果第一行原來有零，將整個第一行置零
        if firstRowHasZero:
            for col in range(n):
                matrix[0][col] = 0

複雜度分析

時間複雜度: 演算法多次遍歷矩陣，每次的複雜度為 $O(m \times n)$，因為是對矩陣進行全盤或部分掃描。由於其分層操作並不超過這個界限，因此時間複雜度為 $O(m \times n)$。
空間複雜度: 該解法使用固定數量的額外空間，表示為 $O(1)$。這是由於只使用了少量的額外變數（如 firstRowHasZero）以及在不使用額外資料結構的情況下就地修改矩陣所致。

CS Note
En

Leetcode 73. Set Matrix Zeroes

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析