给定条件下构造矩阵

标签: 图拓扑排序数组矩阵

难度: Hard

给你一个正整数 k ，同时给你：

一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [above_i, below_i] 和
一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [left_i, right_i] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

对于所有 0 到 n - 1 之间的下标 i ，数字 above_i 所在的行必须在数字 below_i 所在行的上面。
对于所有 0 到 m - 1 之间的下标 i ，数字 left_i 所在的列必须在数字 right_i 所在列的左边。

返回满足上述要求的任意矩阵。如果不存在答案，返回一个空的矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
- 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
- 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 10⁴
rowConditions[i].length == colConditions[i].length == 2
1 <= above_i, below_i, left_i, right_i <= k
above_i != below_i
left_i != right_i

Submission

运行时间: 68 ms

内存: 22.9 MB

def topological_sort(graph):
    n=len(graph)
    # 计算每个节点的入度
    in_degree = [0]*n
    for li in graph:
        for j in li:
            in_degree[j]+=1
    # 初始化一个空队列用于存储入度为0的节点
    queue=deque([i for i in range(n) if in_degree[i]==0])
    # 初始化一个空列表来存储排序结果
    result = []
    # 开始拓扑排序
    while queue:
        node = queue.popleft()
        result.append(node)
        # 更新邻居节点的入度，并将入度为0的邻居加入队列
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    # 如果结果中的节点数量等于图中的节点数量，表示成功排序
    if len(result) == len(graph):
        return result
    else:
        return None  # 图中存在环，无法完成拓扑排序

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        #拓扑排序
        graph_row=[[] for _ in range(k)]
        graph_col=[[] for _ in range(k)]
        for a,b in rowConditions:
            graph_row[a-1].append(b-1)
        res1=topological_sort(graph_row)
        if not res1:
            return []
        for a,b in colConditions:
            graph_col[a-1].append(b-1)
        res2=topological_sort(graph_col)
        if not res2:
            return []
        ans=[[0]*k for _ in range(k)]
        mp=dict()
        for i,v in enumerate(res2):
            mp[v+1]=i
        for i in range(k):
            j=mp[res1[i]+1]
            ans[i][j]=res1[i]+1
        return ans

Explain

题解的核心思想是使用拓扑排序来确定行和列的相对顺序。首先，将 `rowConditions` 和 `colConditions` 分别视为有向图中的边，构建两个图：一个用于行的约束，另一个用于列的约束。然后对这两个图进行拓扑排序。如果图中存在环（即拓扑排序返回空），则说明没有合法的布局满足所有条件，返回空矩阵。如果排序成功，使用排序结果来构建矩阵，其中行排序结果决定数字在矩阵中的行，列排序结果决定数字在矩阵中的列。最后，根据这两个结果构建最终的矩阵。

时间复杂度: O(k^2 + n + m)

空间复杂度: O(k^2 + n + m)

python
def topological_sort(graph):
    n = len(graph)
    in_degree = [0] * n
    for li in graph:
        for j in li:
            in_degree[j] += 1
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(result) == len(graph):
        return result
    else:
        return None

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        graph_row = [[] for _ in range(k)]
        graph_col = [[] for _ in range(k)]
        for a, b in rowConditions:
            graph_row[a-1].append(b-1)
        res1 = topological_sort(graph_row)
        if not res1:
            return []
        for a, b in colConditions:
            graph_col[a-1].append(b-1)
        res2 = topological_sort(graph_col)
        if not res2:
            return []
        ans = [[0] * k for _ in range(k)]
        mp = dict()
        for i, v in enumerate(res2):
            mp[v + 1] = i
        for i in range(k):
            j = mp[res1[i] + 1]
            ans[i][j] = res1[i] + 1
        return ans

Explore

在构建有向图时，每个条件（例如从rowConditions和colConditions中的每一对[a, b]）被转化为从节点a到节点b的一条有向边。这样，每条边恰好表示一个'前后'关系，确保了所有的约束关系都能在图中表达。初始化图结构时，为每个可能的顶点（这里是1到k）创建一个空列表，然后遍历条件列表，将每个条件添加到相应顶点（减1处理因为数组从0开始索引）的邻接表中。这样，构建的图将完全反映了输入的约束关系。

在拓扑排序过程中，我们通过计算每个节点的入度来检测环。初始化时，计算每个节点的入度。在排序过程中，选择入度为0的节点，将其从图中移除，并减少其相邻节点的入度。如果在某一时刻没有入度为0的节点，而图中还有未处理的节点，这表明存在环。另一种检测方法是，如果最终排序的结果数量小于节点总数，也表明图中存在环。

拓扑排序可能有多个有效的结果，这取决于图中节点的相对独立性。如果存在多种有效的拓扑排序，每种排序都可以用来构建一个符合条件的矩阵。解题思路中并未特别处理多个拓扑排序结果；它只是利用了一种可能的排序结果来构建矩阵。在实际应用中，这意味着如果存在多种拓扑排序，可能会有多个符合条件的矩阵解。

使用字典`mp`来映射列位置是基于列的拓扑排序，它应该完全遵循colConditions的约束。这种映射方法确保了每个数字在列的位置是按照列的拓扑排序确定的，因此不会违反初始的列约束。只要拓扑排序正确无误地反映了所有的列约束，使用这种映射方式构建矩阵就不会出现位置错误。