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
```