前言

今天我們要來挑戰一道經典又實用的題目——Set Matrix Zeroes（設定矩陣零）！
這題是 Medium 難度，但它考驗的是我們如何在有限的空間內有效率地修改矩陣。

題目要求我們在一個 m x n 的矩陣中，若某個元素為 0，就將該元素所在的整行和整列都設為 0，而且必須在原地修改，不能另開陣列。
是不是聽起來有點棘手呢？別擔心，我們一起來看解法吧！

英文題目 Set Matrix Zeroes

難度：Medium

題目描述：

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.

給定一個 m x n 的整數矩陣 matrix，如果某個元素為 0，則將它的整行和整列都設為 0。必須在原地進行操作，不允許使用額外的矩陣。

範例 1：

輸入： matrix = [[1,1,1],[1,0,1],[1,1,1]]

輸出： [[1,0,1],[0,0,0],[1,0,1]]

範例 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]]

實作

要解這題，我們需要一個有效率的方法來標記需要置零的行和列，且不能使用額外的空間來儲存標記資訊。
最佳做法是使用矩陣的第一行和第一列作為輔助標記空間：

function setZeroes(matrix: number[][]): void {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let firstRowZero = false;
    let firstColZero = false;

    // 檢查第一列是否有零
    for (let i = 0; i < rows; i++) {
        if (matrix[i][0] === 0) firstColZero = true;
    }

    // 檢查第一行是否有零
    for (let j = 0; j < cols; j++) {
        if (matrix[0][j] === 0) firstRowZero = true;
    }

    // 使用第一行和第一列來標記其他的零
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0; // 標記該行
                matrix[0][j] = 0; // 標記該列
            }
        }
    }

    // 根據標記將相應行和列設為零
    for (let i = 1; i < rows; i++) {
        if (matrix[i][0] === 0) {
            for (let j = 1; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    for (let j = 1; j < cols; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 1; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // 處理第一列
    if (firstColZero) {
        for (let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }

    // 處理第一行
    if (firstRowZero) {
        for (let j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }
}

解題心法

1. 使用第一行和第一列作為標記

   為了避免使用額外的矩陣空間，我們將矩陣的第一行和第一列作為標記工具。當我們遇到一個 0 時，將它的對應行和列的第一個元素設為 0，這樣就標記了該行和列需要被清零。

2. 檢查並標記第一行和第一列

   由於第一行和第一列會被用來標記其他行列，我們需要提前檢查它們是否本身包含 0，並用 firstRowZero 和 firstColZero 這兩個變數來記錄這些狀態。

3. 根據標記清零其他行和列

   接下來，我們根據標記的結果來將對應的行和列設為 0。這樣做時要小心，必須從矩陣的第二行和第二列開始處理，以免影響到我們的標記資訊。

4. 最後處理第一行和第一列

   最後，根據 firstRowZero 和 firstColZero 的狀態決定是否要將整個第一行或第一列設為 0。

為什麼這樣處理？

這種方法利用了矩陣本身的空間來記錄需要清零的位置，避免使用額外的空間。
透過雙重標記和順序處理，我們有效地將問題分解，保證了 O(m * n) 的時間複雜度和 O(1) 的空間複雜度。

試試看優化

function setZeroes(matrix: number[][]): void {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let firstRowZero = false;
    let firstColZero = false;

    // 檢查第一行和第一列是否有零
    for (let i = 0; i < rows; i++) {
        if (matrix[i][0] === 0) firstColZero = true;
    }
    for (let j = 0; j < cols; j++) {
        if (matrix[0][j] === 0) firstRowZero = true;
    }

    // 使用第一行和第一列來標記需要清零的位置
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // 將標記的行設為零
    for (let i = 1; i < rows; i++) {
        if (matrix[i][0] === 0) {
            matrix[i].fill(0);
        }
    }

    // 將標記的列設為零
    for (let j = 1; j < cols; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 0; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // 根據標記清除第一行和第一列
    if (firstColZero) {
        for (let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
    if (firstRowZero) {
        matrix[0].fill(0);
    }
}

優化重點：

1. 整合檢查：將檢查第一行和第一列是否包含零的代碼合併，簡化判斷流程。

2. 使用 .fill(0)：在清空整行時使用 .fill(0) 方法，簡化設零的過程。

3. 保持直觀：清空標記的行與列後，最後根據標記清空第一行與第一列，保持代碼邏輯的簡單與直觀。

這樣的改寫讓程式碼更易於閱讀和理解，同時維持了最佳的時間與空間複雜度。

本次要點：

• 使用矩陣的第一行和第一列來標記需要清零的位置。
• 避免使用額外的空間，保證空間複雜度為 O(1)。
• 順序處理，先標記後清零，最後再處理第一行和第一列。

解完這題是不是對矩陣的操作更有感覺了呢？
透過這些解題技巧，輕鬆掌握複雜的矩陣處理問題，我們下次再見啦！ ヾ(*´∇`)ﾉ