Leetcode 1605. Find Valid Matrix Given Row and Column Sums

1. Description

2. Solution

**解析：**Version 1，貪心算法，由于矩陣中的每一個元素

matrix[i][j]

一定不大于

min(rowSum[i], colSum[j]

，是以将

matrix[i][j]

設定為

min(rowSum[i], colSum[j]

就可以解決一行或一列的數值設定問題，目前行或目前列剩餘的元素為

，周遊所有元素存在重複設定的問題。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/