【LC100】No73. 矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

提示:

• m == matrix.length

• n == matrix[0].length

• 1 <= m, n <= 200

• -231 <= matrix[i][j] <= 231 - 1

示例

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

链接

思路

最简单的办法是，我们进行两次遍历，第一次遍历记录所有 ==0 的元素，第二次遍历修改它所在的行和列。

解法一：标记数组

使用一个 List<int[]> 记录所有 ==0 元素的行列下标。

也可以使用两个 boolean 数组分别标记 ==0 的元素的行和列。

PS：boolean 数组默认 false，所以设置 ==0 元素对应的行列为 true，不用 int 数组是因为 int 数组默认值是 0，无法标识，或者用 int 数组就置为非 0 数。

代码

// class Solution {
//     public void setZeroes(int[][] matrix) {
//         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
//             return;
//         }
//         int m = matrix.length;
//         int n = matrix[0].length;
//         List<int[]> list = new ArrayList<>();
//         for (int i = 0; i < m; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (matrix[i][j] == 0) {
//                     list.add(new int[]{i , j});
//                 }
//             }
//         }
//         for (int[] arr : list) {
//             for (int i = 0; i < m; i++) {
//                 matrix[i][arr[1]] = 0;
//             }
//             for (int j = 0; j < n; j++) {
//                 matrix[arr[0]][j] = 0;
//             }
//         }
//         return;
//     }
// }

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        return;
    }
}

• 时间复杂度：O(mn)

• 空间复杂度：O(m + n)