Problem :

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.

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. 獲取矩陣的行列數
2. 創建兩個集合儲存需設置為0的元素
3. 遍歷矩陣中的元素檢查需要設置為0的行跟列，並檢查當前元素是否為0，最後將行與列索引分別放入行與列的集合中
4. 遍歷矩陣將檢查的元素設置為0，如果當前行或列在對應的集合當中，將當前和目標元素設置為0

程式碼 :

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        //獲取矩陣的行數
        int n = matrix.size();
        //獲取矩陣的列數
        int m = matrix[0].size();
        //創建兩個集合
        set<int>row, column;
        //遍歷矩陣中的元素檢查需要設置為0的行跟列
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //檢查當前元素是否為0
                if(matrix[i][j] == 0){
                    //將行索引添加到行集合中
                    row.insert(i);
                    //將列索引添加到列集合中
                    column.insert(j);
                }
            }
        }
        //遍歷矩陣將檢查的元素設置為0
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //如果當前行或列在對應的集合中，將該元素設置為0
                if(row.count(i) || column.count(j)){
                    //將當前元素設置為0
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

結論 :

這題的目標是將矩陣中任何包含0的行和列中的所有元素設置為0，過程使用集合來記錄需要改變的行與列索引，時間複雜度為O(n * m)，n是行數，m是列數，因此需要將矩陣遍歷兩次。