2392. Build a Matrix With Conditions
## 思路
k*k的Matrix 1~k 只會出現一次, 其餘補0
兩個conditions又各自獨立
分別產生graph 做topological sort產生兩個array
如果array長度不足k 表示condition有衝突, 回傳 []
再根據順序把值塞進matrix
## Complexity
N = conditions個數
TopoSort:
Time: O(N+k) # O(V+E)
Space: O(N+k)
建Matrix:
Time, Space: O(k^2)
填入Matrix:
Time: O(k)
Time, Space: O( Max(N+k, k^2))
## Code
```python
class Solution:
def buildMatrix(self, k: int, rowConditions: List[List[int]],
colConditions: List[List[int]]) -> List[List[int]]:
def topo(conditions):
graph = defaultdict(list)
in_degree = [0] * (1+k)
for _from, _to in conditions:
graph[_from].append(_to)
in_degree[_to] += 1
res = []
queue = deque([i for i in range(1, 1+k) if in_degree[i] == 0])
while queue:
node = queue.popleft()
res.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return res
rows = topo(rowConditions)
cols = topo(colConditions)
if len(rows) != k or len(cols) != k:
return []
res = [[0] * k for _ in range(k)]
val_to_ridx = {val: ri for ri, val in enumerate(rows)}
for ci, val, in enumerate(cols):
ri = val_to_ridx[val]
res[ri][ci] = val
return res
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.221 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721543045.A.702.html