🔗 🟢 3033. Modify the Matrix 1181

tags: `Weekly Contest 384` `陣列(Array)` `矩陣(Matrix)`

題意

給定一個大小為 $m \times n$ 的整數矩陣 $\text{matrix}$ ，下標從 $0$ 開始。新建一個大小同樣為 $m \times n$ 的整數矩陣 $\text{answer}$ ，使 $\text{answer}$ 與 $\text{matrix}$ 相等，接著將其中每個值為 $-1$ 的元素替換為所在 直行(column) 的最大元素。

返回矩陣 $\text{answer}$ 。

約束條件

$m == \text{matrix.length}$
$n == \text{matrix[i].length}$
$2 \leq m, n \leq 50$
$-1 \leq \text{matrix[i][j]} \leq 100$
每個 column 至少包含一個非負整數。

思路：維護每個 column 的最大值

由於需要將每個值為 $-1$ 的元素替換為所在 column 的最大值，因此我們需要先使用一個大小為 $n$ 的陣列 $mx$ 來維護每個 column 的最大值。

接著重新遍歷整個矩陣，對於每個元素，如果它的值是 $-1$ ，就將其替換為該 column 的最大值；否則保留原值。

複雜度分析

時間複雜度： $O(m \times n)$ ，需要遍歷整個矩陣兩次，一次是計算每個 column 的最大值，一次是生成新的矩陣 $\text{answer}$ 。
空間複雜度： $O(n)$ ，用於存儲 $mx$ 陣列。

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        mx = [max([matrix[i][j] for i in range(m)]) for j in range(n)]
        return [[matrix[i][j] if matrix[i][j] != -1 else mx[j] for j in range(n)] for i in range(m)]

class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> mx(n, INT_MIN);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                mx[j] = max(mx[j], matrix[i][j]);
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ans[i][j] = (matrix[i][j] == -1) ? mx[j] : matrix[i][j];
        return ans;
    }
};