LeetCode 每日一题笔记 日期：2025.03.24 题目：2906.构造乘积矩阵

LeetCode 每日一题笔记0. 前言日期2025.03.24题目2906.构造乘积矩阵难度中等标签数组 矩阵 前缀和1. 题目理解问题描述给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵grid定义一个下标从 0 开始、大小为 n * m 的二维矩阵p。如果满足以下条件则称p为grid的乘积矩阵对于每个元素p[i][j]它的值等于除了grid[i][j]外所有元素的乘积且乘积对12345取余数。返回grid的乘积矩阵。示例输入grid [[1,2],[3,4]]输出[[24,12],[8,6]]解释p[0][0] grid[0][1] * grid[1][0] * grid[1][1] 2 * 3 * 4 24p[0][1] grid[0][0] * grid[1][0] * grid[1][1] 1 * 3 * 4 12p[1][0] grid[0][0] * grid[0][1] * grid[1][1] 1 * 2 * 4 8p[1][1] grid[0][0] * grid[0][1] * grid[1][0] 1 * 2 * 3 62. 解题思路核心观察暴力求解的问题若直接对每个元素grid[i][j]遍历所有元素计算乘积排除自身时间复杂度为O((n∗m)2)O((n*m)^2)O((n∗m)2)。当矩阵规模较大时如 n、m 为 1000计算量会达到101210^{12}1012级别远超时间限制且多次乘法会导致数值溢出即使取模也无法降低时间复杂度。前缀/后缀乘积优化将二维矩阵展平为一维数组通过「前缀乘积数组」和「后缀乘积数组」快速计算每个位置排除自身的总乘积前缀乘积pre[i]表示一维数组中前i个元素的乘积包含i后缀乘积suf[i]表示一维数组中从i到末尾的乘积包含i对于位置k排除自身的总乘积 前缀乘积pre[k-1]* 后缀乘积suf[k1]边界位置单独处理。算法步骤展平矩阵将二维矩阵grid转换为一维数组arr便于统一计算前缀/后缀乘积计算前缀乘积pre[0] arr[0]pre[i] (pre[i-1] * arr[i]) % 12345计算后缀乘积suf[len-1] arr[len-1]suf[i] (suf[i1] * arr[i]) % 12345重构结果矩阵遍历每个位置根据前缀/后缀乘积计算排除自身的总乘积转换回二维矩阵并取模。3. 代码实现packagecom.sheeta1998.lec.lc2906;classSolution{publicint[][]constructProductMatrix(int[][]grid){intngrid.length;// 矩阵行数intmgrid[0].length;// 矩阵列数inttotaln*m;// 一维数组总长度int[]arrnewint[total];int[]prenewint[total];// 前缀乘积数组int[]sufnewint[total];// 后缀乘积数组// 步骤1将二维矩阵展平为一维数组intidx0;for(inti0;in;i){for(intj0;jm;j){arr[idx]grid[i][j];}}// 步骤2计算前缀乘积pre[0]arr[0]%12345;for(inti1;itotal;i){pre[i](pre[i-1]*arr[i])%12345;}// 步骤3计算后缀乘积suf[total-1]arr[total-1]%12345;for(intitotal-2;i0;i--){suf[i](suf[i1]*arr[i])%12345;}// 步骤4重构乘积矩阵idx0;for(inti0;in;i){for(intj0;jm;j){if(idx0){// 第一个元素只有后缀乘积grid[i][j]suf[1]%12345;}elseif(idxtotal-1){// 最后一个元素只有前缀乘积grid[i][j]pre[total-2]%12345;}else{// 中间元素前缀*后缀grid[i][j](pre[idx-1]*suf[idx1])%12345;}idx;}}returngrid;}}4. 代码优化说明空间优化原代码中prearr/sufarr命名简化为pre/suf变量名更直观取模时机每一步乘法后立即对12345取模避免整数溢出Java 中 int 最大值约2×1092×10^92×109多次乘法易溢出边界处理明确区分第一个/最后一个元素的计算逻辑避免数组越界变量复用直接修改原矩阵grid存储结果无需额外创建二维数组节省空间。5. 复杂度分析时间复杂度O(n×m)O(n×m)O(n×m)。展平矩阵、计算前缀/后缀乘积、重构矩阵均为一次遍历总次数为3×n×m3×n×m3×n×m属于线性时间复杂度空间复杂度O(n×m)O(n×m)O(n×m)。需要额外存储一维数组arr、前缀数组pre、后缀数组suf总空间为3×n×m3×n×m3×n×m可进一步优化为O(1)O(1)O(1)空间直接在二维矩阵上计算前缀/后缀但代码可读性降低。6. 总结暴力求解不可行的原因时间复杂度为O((n×m)2)O((n×m)^2)O((n×m)2)矩阵规模较大时会超时且多次乘法易导致数值溢出核心优化思路利用「前缀/后缀乘积」将时间复杂度降至线性通过展平二维矩阵简化计算逻辑关键细节每一步乘法后取模避免溢出边界位置单独处理防止数组越界。关键点回顾暴力解法因O((n∗m)2)O((n*m)^2)O((n∗m)2)时间复杂度无法通过大规模用例必须用前缀/后缀乘积优化展平二维矩阵是简化前缀/后缀计算的核心技巧最终需还原为二维结果取模操作需在每一步乘法后执行避免整数溢出且满足题目要求。