→ Lilchicken: 錢 07/20 12:31
→ dont: 發過ㄌ 07/20 12:38
1605. Find Valid Matrix Given Row and Column Sums
## 思路
matrix[r][c] 可以塞的值介於[0, min(rowSum[r], colSum[c])]
直接Greedy塞這範圍的最大值
再更新rowSum, colSum (減掉 matrix[r][c])
## Complexity
Time, Space: O(MN) # aux space: O(1)
如果用two pointer會快一點
(ex. rowSum[r]=0時, 這個row後面也都會是0 所以可以直接跳過)
不過時間複雜度一樣是O(MN)
## Code
```python
class Solution:
def restoreMatrix(self, rowSum: List[int], colSum: List[int]) ->
List[List[int]]:
len_r = len(rowSum)
len_c = len(colSum)
res = [[0] * len_c for _ in range(len_r)]
for r in range(len_r):
for c in range(len_c):
res[r][c] = min(rowSum[r], colSum[c])
rowSum[r] -= res[r][c]
colSum[c] -= res[r][c]
return res
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.232 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721449871.A.20A.html