Easy

题目描述

给定一个下标从 0 开始的 m x n 整数矩阵 matrix，创建一个新的下标从 0 开始的矩阵 answer。使 answer 等于 matrix，然后将每个值为 -1 的元素替换为其所在列的最大元素。

返回矩阵 answer。

示例 1：

输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
输出：[[1,2,9],[4,8,6],[7,8,9]]
解释：上图显示了被更改的元素（蓝色）。
- 我们将单元格 [1][1] 中的值替换为列 1 中的最大值，即 8。
- 我们将单元格 [0][2] 中的值替换为列 2 中的最大值，即 9。

示例 2：

输入：matrix = [[3,-1],[5,2]]
输出：[[3,2],[5,2]]
解释：上图显示了被更改的元素（蓝色）。

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 2 <= m, n <= 50
  • -1 <= matrix[i][j] <= 100
  • 输入保证每一列至少包含一个非负整数。

解题思路

这道题的解题思路比较直观，需要分两个步骤来解决：

第一步：计算每列的最大值 遍历整个矩阵，对每一列找到除了 -1 以外的最大值。由于题目保证每列至少有一个非负整数，所以一定能找到有效的最大值。

第二步：替换 -1 元素 再次遍历矩阵，将所有值为 -1 的元素替换为其所在列的最大值。

算法流程：

  1. 初始化一个数组 colMax 存储每列的最大值，初始值设为较小值（如 -1）
  2. 第一次遍历：对每个位置 (i,j)，如果 matrix[i][j] != -1，则更新 colMax[j]
  3. 第二次遍历：对每个位置 (i,j)，如果 matrix[i][j] == -1，则将其设为 colMax[j]

这种两遍扫描的方法时间复杂度为 O(m×n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> colMax(n, -1);
        
        // 计算每列的最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != -1) {
                    colMax[j] = max(colMax[j], matrix[i][j]);
                }
            }
        }
        
        // 替换 -1 为对应列的最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = colMax[j];
                }
            }
        }
        
        return matrix;
    }
};

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        col_max = [-1] * n
        
        # 计算每列的最大值
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != -1:
                    col_max[j] = max(col_max[j], matrix[i][j])
        
        # 替换 -1 为对应列的最大值
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == -1:
                    matrix[i][j] = col_max[j]
        
        return matrix

public class Solution {
    public int[][] ModifiedMatrix(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[] colMax = new int[n];
        Array.Fill(colMax, -1);
        
        // 计算每列的最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != -1) {
                    colMax[j] = Math.Max(colMax[j], matrix[i][j]);
                }
            }
        }
        
        // 替换 -1 为对应列的最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = colMax[j];
                }
            }
        }
        
        return matrix;
    }
}

var modifiedMatrix = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const answer = matrix.map(row => [...row]);
    
    for (let col = 0; col < n; col++) {
        let maxVal = -1;
        for (let row = 0; row < m; row++) {
            if (matrix[row][col] !== -1) {
                maxVal = Math.max(maxVal, matrix[row][col]);
            }
        }
        for (let row = 0; row < m; row++) {
            if (answer[row][col] === -1) {
                answer[row][col] = maxVal;
            }
        }
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历矩阵两次，每次都是 O(m × n)
空间复杂度O(n)需要额外的数组存储每列的最大值