原地实现矩阵置零｜Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 73. 矩阵置零 ，难度为中等。

Tag : 「模拟」

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

进阶：

一个直观的解决方案是使用 $O(m * n)$ 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 $O(m + n)$ 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

示例 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]]
复制代码

提示：

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

前言

由于 $O(m*n)$ 和 $O(m+n)$ 空间的解法都十分简单，无非是「同等大小的矩阵」或「与行列数量相等的标识」来记录置零信息。

这里着重讲解利用原矩阵的 $O(1)$ 空间解法。

O(1) 空间解法

1. 使用两个变量（r0 & c0），记录「首行 & 首列」是否该被置零

2.「非首行首列」的位置

将置零信息存储到原矩阵
根据置零信息，置零「非首行首列」的位置

3. 使用 r0 & c0 ，置零「首行 & 首列」

代码：

class Solution {
    public void setZeroes(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        // 1. 扫描「首行」和「首列」记录「首行」和「首列」是否该被置零
        boolean r0 = false, c0 = false;
        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 0) {
                r0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                c0 = true;
                break;
            }
        }

        // 2.1 扫描「非首行首列」的位置，如果发现零，将需要置零的信息存储到该行的「最左方」和「最上方」的格子内
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = mat[0][j] = 0;
                }
            }
        }
        // 2.2 根据刚刚记录在「最左方」和「最上方」格子内的置零信息，进行「非首行首列」置零
        for (int j = 1; j < n; j++) {
            if (mat[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    mat[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (mat[i][0] == 0) {
                Arrays.fill(mat[i], 0);
            }
        }
        
        // 3. 根据最开始记录的「首行」和「首列」信息，进行「首行首列」置零
        if (r0) for (int i = 0; i < m; i++) mat[i][0] = 0;
        if (c0) Arrays.fill(mat[0], 0);
    }
}
复制代码