原文題目

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.

題目摘要

1. 問題描述：給定一個 m x n 的整數矩陣 matrix，如果某個元素為 0，則將其所在的整列和整欄都設為 0。你必須在原地完成這項操作。
2. 輸入：一個 m x n 的整數矩陣 matrix。
3. 輸出：將矩陣中的元素依照要求設為 0，直接修改原矩陣，不需回傳結果。

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解題思路

1. 設定標記：
   • 先掃描第一列和第一欄，確認是否本身需要被設為 0，因為這兩個會在之後被用來當作標記。
   • 從第二列第二欄開始掃描矩陣，若發現某個元素為 0，則將該元素所在的列和欄的第一個元素設為 0，作為標記。
2. 根據標記處理轉換0：
   • 再次掃描矩陣，依照標記將對應的列和欄設為 0。
   • 最後根據一開始的判斷，處理是否需要將第一列和第一欄設為 0。

程式碼

class Solution {
    public void setZeroes(int[][] matrix) {
        //定義兩boolean值標記第一列和第一欄是否包含0
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        //第一欄若有0，將firstColHasZero設為true
        for (int i=0; i<matrix.length; i++) { 
            if (matrix[i][0]==0) {
                firstColHasZero = true;
            }
        }
        //第一列若有0，將firstRowHasZero設為 true
        for (int j=0; j<matrix[0].length; j++) { 
            if (matrix[0][j]==0) {
                firstRowHasZero = true;
            }
        }
        //如果matrix[i][j]為0，將對應的第一列和第一欄的元素設為0
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) { 
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //根據第一列和第一欄的標記，將對應的行和列設為0
        for (int i = 1; i < matrix.length; i++) { 
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (firstRowHasZero) { //如果firstRowHasZero是true
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0; //將第一列的所有元素設為0
            }
        }
        if (firstColHasZero) { //如果firstColHasZero是true
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0; //將第一欄的所有元素設為0
            }
        }
    }
}

結論： 在寫這題其實就是在說「標記」的重要性，想像一下，你在整理房間時發現幾個角落有問題，為了不弄亂整個房間，你先用便利貼標記出這些問題區域，然後再一步步處理，這樣就不用來回檢查。這題也是類似的概念，我們透過第一列和第一欄來標記哪些行和列需要改動，等所有該標記的地方都標好了，再回頭一次性把它們全改掉。這不僅節省時間，也避免不必要的操作。