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 = 0j = 0while i < m and j < n:if rowSum[i] > colSum[j]:matrix[i][j] = colSum[j]rowSum[i] -= colSum[j]j += 1elif rowSum[i] < colSum[j]:matrix[i][j] = rowSum[i]colSum[j] -= rowSum[i]i += 1else:matrix[i][j] = rowSum[i]i += 1j += 1return matrix

Reference

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