Hard

题目描述

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

  • 一个大小为 n 的二维整数数组 rowConditions，其中 rowConditions[i] = [abovei, belowi]
  • 一个大小为 m 的二维整数数组 colConditions，其中 colConditions[i] = [lefti, righti]

这两个数组都包含从 1 到 k 的整数。

你需要构造一个 k x k 的矩阵，该矩阵包含从 1 到 k 的每个数字恰好一次。剩余的单元格应该为 0。

矩阵还应满足以下条件：

  • 对于所有从 0 到 n - 1 的 i，数字 abovei 应出现在严格位于数字 belowi 所在行上方的行中。
  • 对于所有从 0 到 m - 1 的 i，数字 lefti 应出现在严格位于数字 righti 所在列左侧的列中。

返回满足条件的任意矩阵。如果不存在答案，返回一个空矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]

提示：

  • 2 <= k <= 400
  • 1 <= rowConditions.length, colConditions.length <= 10^4
  • rowConditions[i].length == colConditions[i].length == 2
  • 1 <= abovei, belowi, lefti, righti <= k
  • abovei != belowi
  • lefti != righti

解题思路

这道题的核心思路是将行条件和列条件分别看作有向图，使用拓扑排序来确定元素的相对位置。

算法步骤

  1. 构建有向图：

    • 对于行条件 [above, below]，在行图中添加边 above → below
    • 对于列条件 [left, right]，在列图中添加边 left → right

  2. 拓扑排序：

    • 对行图和列图分别进行拓扑排序
    • 如果存在环（即拓扑排序失败），说明无解，返回空矩阵
    • 拓扑排序的结果给出了元素在行/列上的相对顺序

  3. 构造矩阵：

    • 根据拓扑排序结果，确定每个数字在矩阵中的行位置和列位置
    • 将数字 1 到 k 依次放入对应的位置

关键点

  • 检测环：如果条件中存在矛盾（如示例2中的 1→2→3→1），拓扑排序会失败
  • 位置映射：拓扑排序给出的是相对顺序，需要将其映射到具体的行列索引
  • 矩阵填充：只有数字 1 到 k 的位置需要填充，其余位置保持为 0

时间复杂度为 O(k + n + m)，其中 n 和 m 分别是行条件和列条件的数量。空间复杂度为 O(k²)，主要用于存储结果矩阵。

代码实现

class Solution {
public:
    vector<int> topologicalSort(int k, vector<vector<int>>& conditions) {
        vector<vector<int>> graph(k + 1);
        vector<int> indegree(k + 1, 0);
        
        for (auto& condition : conditions) {
            graph[condition[0]].push_back(condition[1]);
            indegree[condition[1]]++;
        }
        
        queue<int> q;
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);
            
            for (int neighbor : graph[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return result.size() == k ? result : vector<int>();
    }
    
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rowOrder = topologicalSort(k, rowConditions);
        vector<int> colOrder = topologicalSort(k, colConditions);
        
        if (rowOrder.empty() || colOrder.empty()) {
            return {};
        }
        
        vector<int> rowPos(k + 1), colPos(k + 1);
        for (int i = 0; i < k; i++) {
            rowPos[rowOrder[i]] = i;
            colPos[colOrder[i]] = i;
        }
        
        vector<vector<int>> matrix(k, vector<int>(k, 0));
        for (int i = 1; i <= k; i++) {
            matrix[rowPos[i]][colPos[i]] = i;
        }
        
        return matrix;
    }
};

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topological_sort(conditions):
            graph = [[] for _ in range(k + 1)]
            indegree = [0] * (k + 1)
            
            for above, below in conditions:
                graph[above].append(below)
                indegree[below] += 1
            
            queue = deque()
            for i in range(1, k + 1):
                if indegree[i] == 0:
                    queue.append(i)
            
            result = []
            while queue:
                node = queue.popleft()
                result.append(node)
                
                for neighbor in graph[node]:
                    indegree[neighbor] -= 1
                    if indegree[neighbor] == 0:
                        queue.append(neighbor)
            
            return result if len(result) == k else []
        
        row_order = topological_sort(rowConditions)
        col_order = topological_sort(colConditions)
        
        if not row_order or not col_order:
            return []
        
        row_pos = [0] * (k + 1)
        col_pos = [0] * (k + 1)
        
        for i in range(k):
            row_pos[row_order[i]] = i
            col_pos[col_order[i]] = i
        
        matrix = [[0] * k for _ in range(k)]
        for i in range(1, k + 1):
            matrix[row_pos[i]][col_pos[i]] = i
        
        return matrix

public class Solution {
    public int[][] BuildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        var rowOrder = TopologicalSort(k, rowConditions);
        var colOrder = TopologicalSort(k, colConditions);
        
        if (rowOrder.Length == 0 || colOrder.Length == 0) {
            return new int[0][];
        }
        
        var rowPos = new int[k + 1];
        var colPos = new int[k + 1];
        
        for (int i = 0; i < k; i++) {
            rowPos[rowOrder[i]] = i;
            colPos[colOrder[i]] = i;
        }
        
        var matrix = new int[k][];
        for (int i = 0; i < k; i++) {
            matrix[i] = new int[k];
        }
        
        for (int i = 1; i <= k; i++) {
            matrix[rowPos[i]][colPos[i]] = i;
        }
        
        return matrix;
    }
    
    private int[] TopologicalSort(int k, int[][] conditions) {
        var graph = new List<int>[k + 1];
        var indegree = new int[k + 1];
        
        for (int i = 0; i <= k; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var condition in conditions) {
            graph[condition[0]].Add(condition[1]);
            indegree[condition[1]]++;
        }
        
        var queue = new Queue<int>();
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        var result = new List<int>();
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            result.Add(node);
            
            foreach (var neighbor in graph[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        return result.Count == k ? result.ToArray() : new int[0];
    }
}

var buildMatrix = function(k, rowConditions, colConditions) {
    function topologicalSort(conditions, k) {
        const graph = new Map();
        const indegree = new Array(k + 1).fill(0);
        
        for (let i = 1; i <= k; i++) {
            graph.set(i, []);
        }
        
        for (const [from, to] of conditions) {
            graph.get(from).push(to);
            indegree[to]++;
        }
        
        const queue = [];
        for (let i = 1; i <= k; i++) {
            if (indegree[i] === 0) {
                queue.push(i);
            }
        }
        
        const result = [];
        while (queue.length > 0) {
            const node = queue.shift();
            result.push(node);
            
            for (const neighbor of graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] === 0) {
                    queue.push(neighbor);
                }
            }
        }
        
        return result.length === k ? result : null;
    }
    
    const rowOrder = topologicalSort(rowConditions, k);
    const colOrder = topologicalSort(colConditions, k);
    
    if (!rowOrder || !colOrder) {
        return [];
    }
    
    const rowPos = new Map();
    const colPos = new Map();
    
    for (let i = 0; i < k; i++) {
        rowPos.set(rowOrder[i], i);
        colPos.set(colOrder[i], i);
    }
    
    const matrix = Array(k).fill(0).map(() => Array(k).fill(0));
    
    for (let num = 1; num <= k; num++) {
        const row = rowPos.get(num);
        const col = colPos.get(num);
        matrix[row][col] = num;
    }
    
    return matrix;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k + n + m)n和m分别是行条件和列条件的数量，拓扑排序的时间复杂度
空间复杂度O(k²)主要用于存储结果矩阵和图的邻接表

相关题目