跳到主要内容
极客日志极客日志
首页博客AI提示词GitHub精选代理工具
|注册
博客列表

目录

  1. LeetCode 解题：矩阵置零（O(1) 空间复杂度）
  2. 一、问题背景：明确「矩阵置零」题目要求
  3. 题目示例
  4. 二、基础思路的不足
  5. 三、核心优化思路：复用第一行 / 第一列作为标记
  6. 四、完整解题逻辑（含关键修复点）
  7. 步骤 1：初始化变量
  8. 步骤 2：标记阶段（遍历矩阵，记录需要置零的行 / 列）
  9. 步骤 3：置零阶段（处理第二行第二列及以后的元素）
  10. 步骤 4：修复点 1 — 处理第一列的置零
  11. 步骤 5：修复点 2 — 处理第一行的置零
  12. 五、完整源码
Javajava算法

LeetCode 73 矩阵置零：O(1) 空间复杂度解法

本文讲解 LeetCode 73 矩阵置零问题的 O(1) 空间复杂度解法。核心难点在于原地操作且不使用额外数组。解决方案是利用矩阵的第一行和第一列作为标记位，记录需要置零的行和列。通过引入独立变量处理第一行是否存在零的情况，避免覆盖原始数据。算法分为初始化、标记阶段、置零阶段及边界修复四个步骤，最终实现高效的空间优化。

极客零度发布于 2026/3/29更新于 2026/4/131 浏览

LeetCode 解题：矩阵置零（O(1) 空间复杂度）

在二维数组（矩阵）类算法题中，矩阵置零 (LeetCode 73) 是一道经典的「空间优化」题目，核心难点在于要求原地操作（空间复杂度 O(1)） —— 即不能额外开辟与矩阵行列数相当的数组来记录需要置零的行和列。该题常见思路包括「额外数组标记」的基础方案，但不符合空间优化要求。最优解利用「矩阵自身第一行 / 第一列做标记」的核心逻辑，完美实现 O(1) 空间复杂度。

一、问题背景：明确「矩阵置零」题目要求

给定一个 m x n 的矩阵 matrix，如果一个元素为 0，那么将其所在的整行和整列都设置为 0。要求在原矩阵上完成操作，且尽可能优化空间复杂度（进阶要求：O(1) 空间复杂度）。

题目示例

输入：

matrix = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]

输出：

[
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

输入：

matrix = [
  [0, 1, 2, 0],
  [3, 4, 5, 2],
  [1, 3, 1, 5]
]

输出：

[
  [0, 0, 0, 0],
  [0, 4, 5, 0],
  [0, 3, , ]
]
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog

更多推荐文章

查看全部
  • 堆（Heap）的实现：基于完全二叉树的顺序存储与调整算法
  • 无人机路径规划算法详解
  • 基于STM32和FreeRTOS的智能手环项目设计与实现
  • C# 调用 OpenAI 大模型实战：从 Demo 到企业级封装
  • 机器人多备用电池与主电池不断电切换管理模块原理及应用
  • Windows 内网环境离线安装 MySQL 完整指南
  • OpenClaw 本地 AI 助手飞书对接部署指南

相关免费在线工具

  • Keycode 信息

    查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online

  • Escape 与 Native 编解码

    JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online

  • JavaScript / HTML 格式化

    使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online

  • JavaScript 压缩与混淆

    Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

1
0

二、基础思路的不足

拿到这道题，最直观的思路是「额外数组标记法」：

  1. 定义两个数组 zeroRows（记录需要置零的行）、zeroCols（记录需要置零的列）；
  2. 遍历矩阵，遇到元素为 0 时，标记对应行和列；
  3. 再次遍历矩阵，根据标记数组将对应行 / 列置零。

该思路的优点是逻辑简单、不易出错，但空间复杂度为 O(m + n)（m 为行数，n 为列数），不符合「O(1) 空间」的进阶要求。因此需要找到「利用矩阵自身空间做标记」的优化思路。

三、核心优化思路：复用第一行 / 第一列作为标记

最优解的核心是用矩阵自身的第一行和第一列代替额外的标记数组，从而将空间复杂度降到 O(1)。但需要解决一个关键冲突：

  • 第一行和第一列本身也可能存在 0，直接用它们做标记会覆盖原始值，导致后续判断错误；
  • 解决方案：用一个独立变量 zero 标记「第一行是否存在 0」，而第一列的标记则复用 matrix[0][0]（即 matrix[0][0] = 0 表示第一列需要置零）。

四、完整解题逻辑（含关键修复点）

标准解题流程分为 5 个核心步骤：

步骤 1：初始化变量
  • rowLength：矩阵的总行数（外层数组长度）；
  • colLength：矩阵的总列数（每行子数组的长度）；
  • zero：标记第一行是否存在 0，初始值为 1（1 表示无 0，0 表示有 0）。
步骤 2：标记阶段（遍历矩阵，记录需要置零的行 / 列）

遍历整个矩阵，遇到元素 matrix[i][m] == 0 时：

  • 标记该列需要置零：将 matrix[0][m] 设为 0；
  • 若该元素在第一行（i == 0）：将 zero 设为 0（标记第一行需要置零）；
  • 若该元素不在第一行：将 matrix[i][0] 设为 0（标记该行需要置零）。
步骤 3：置零阶段（处理第二行第二列及以后的元素）

从第二行（i = 1）、第二列（m = 1）开始遍历矩阵：

  • 若 matrix[i][0] == 0（该行标记为需要置零）或 matrix[0][m] == 0（该列标记为需要置零），则将 matrix[i][m] 置为 0。
  • 此步骤避开第一行第一列，防止标记值被提前覆盖。
步骤 4：修复点 1 — 处理第一列的置零

根据 matrix[0][0] 的值判断第一列是否需要置零：

  • 若 matrix[0][0] == 0，则将第一列中除第一行外的所有元素置零（i >= 1）；
  • 需先处理第一列，再处理第一行，避免第一行置零后覆盖 matrix[0][0] 的标记值。
步骤 5：修复点 2 — 处理第一行的置零

根据 zero 变量的值判断第一行是否需要置零：

  • 若 zero == 0，则将第一行所有元素置零；
  • 注意：循环边界应使用列数 colLength（而非行数），确保遍历第一行所有列。

五、完整源码

class Solution {
    public void setZeroes(int[][] matrix) {
        // 1. 初始化变量：获取矩阵行列数，标记第一行是否有 0
        int rowLength = matrix.length;      // 矩阵总行数
        int colLength = matrix[0].length;   // 矩阵总列数
        int zero = 1;                       // 标记第一行是否有 0，1=无 0，0=有 0

        // 2. 标记阶段：遍历矩阵，用第一行/第一列记录需要置零的行/列
        for (int i = 0; i < rowLength; i++) {
            for (int m = 0; m < colLength; m++) {
                if (matrix[i][m] == 0) {
                    matrix[0][m] = 0;       // 标记第 m 列需要置零
                    if (i == 0) {
                        zero = 0;           // 第一行有 0，更新标记变量
                    } else {
                        matrix[i][0] = 0;   // 标记第 i 行需要置零
                    }
                }
            }
        }

        // 3. 置零阶段：处理第二行第二列及以后的元素（避开第一行第一列）
        for (int i = 1; i < rowLength; i++) {
            for (int m = 1; m < colLength; m++) {
                if (matrix[i][0] == 0 || matrix[0][m] == 0) {
                    matrix[i][m] = 0;
                }
            }
        }

        // 4. 修复点 1：先处理第一列（避免第一行置零覆盖 matrix[0][0]）
        if (matrix[0][0] == 0) {
            for (int i = 1; i < rowLength; i++) {
                matrix[i][0] = 0;
            }
        }

        // 5. 修复点 2：处理第一行（修正循环边界：用列数 colLength 而非行数）
        if (zero == 0) {
            for (int m = 0; m < colLength; m++) {
                matrix[0][m] = 0;
            }
        }
    }
}
FPGA 入门：CAN 总线原理与 Verilog 代码实现
  • Qt C++ QRegularExpression 正则表达式使用详解
  • Spring Boot RESTful API 开发与测试
  • SWC：基于 Rust 的 Web 前端编译工具链解析
  • VR 音游音符轨道系统开发实录与原理解析
  • AD4630 四通道 SPI 模式配置与采集 FPGA 设计
  • 基于 Nexent 知识库与 MCP 生态打造智能烹饪顾问实战
  • 我用 Nexent 做了个 AI 大厨：基于 Nexent 知识库与 MCP 生态打造智能烹饪顾问实战
  • 35 道常见前端 Vue 面试题详解
  • OpenClaw 统一接入飞书钉钉 WhatsApp 打造 AI 指挥中心
  • K-RagRec：基于知识图谱检索增强生成的 LLM 推荐系统
  • （6-4-02）IMU融合与机体状态估计：综合实战：腿式机器人的IMU关节融合与状态估计（2）
  • Python 爬取微信公众号：合法性、风险与反爬真相