Leetcode 1605. Find Valid Matrix Given Row and Column Sums

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，贪心算法，由于矩阵中的每一个元素matrix[i][j]一定不大于min(rowSum[i], colSum[j]，因此将matrix[i][j]设置为min(rowSum[i], colSum[j]就可以解决一行或一列的数值设置问题，当前行或当前列剩余的元素为0，遍历所有元素存在重复设置的问题。Version 2进行了优化，减少了重复设置的问题，如果输出Version 1最终的rowSum, colSum，会发现所有的元素都变为了0，而Version 2的则不是，Version对于不再用到的rowSum[i], colSum[j]，没有减去matrix[i][j]。

• Version 1

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m = len(rowSum)
        n = len(colSum)
        matrix = [n * [0] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                matrix[i][j] = min(rowSum[i], colSum[j])
                rowSum[i] -= matrix[i][j]
                colSum[j] -= matrix[i][j]
        return matrix

• Version 2

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m = len(rowSum)
        n = len(colSum)
        matrix = [n * [0] for _ in range(m)]
        i = 0
        j = 0
        while i < m and j < n:
            if rowSum[i] > colSum[j]:
                matrix[i][j] = colSum[j]
                rowSum[i] -= colSum[j]
                j += 1
            elif rowSum[i] < colSum[j]:
                matrix[i][j] = rowSum[i]
                colSum[j] -= rowSum[i]
                i += 1
            else:
                matrix[i][j] = rowSum[i]
                i += 1
                j += 1
        return matrix

Reference

1. https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/