python3 解法, 执行用时: 160 ms, 内存消耗: 22.7 MB, 提交时间: 2023-06-26 09:59:56

from graphlib import TopologicalSorter

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def get_pos(cons: List[List[int]]) -> List[int]:
            ts = TopologicalSorter()
            for x in range(1, k + 1):
                ts.add(x)
            for x, y in cons:
                ts.add(y, x)
            pos = [0] * (k + 1)
            for i, x in enumerate(ts.static_order()):
                pos[x] = i
            return pos

        try:
            res = [[0] * k for _ in range(k)]
            for x, (i, j) in enumerate(zip(get_pos(rowConditions), get_pos(colConditions))): res[i][j] = x
            return res
        except:
            return []

golang 解法, 执行用时: 88 ms, 内存消耗: 7.6 MB, 提交时间: 2023-06-26 09:57:11

func topoSort(k int, edges [][]int) []int {
	g := make([][]int, k)
	inDeg := make([]int, k)
	for _, e := range edges {
		x, y := e[0]-1, e[1]-1 // 顶点编号从 0 开始，方便计算
		g[x] = append(g[x], y)
		inDeg[y]++
	}
	q := make([]int, 0, k)
	orders := q // 复用队列作为拓扑序
	for i, d := range inDeg {
		if d == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			if inDeg[y]--; inDeg[y] == 0 {
				q = append(q, y)
			}
		}
	}
	if cap(q) > 0 {
		return nil
	}
	return orders[:k]
}

func buildMatrix(k int, rowConditions, colConditions [][]int) [][]int {
	row := topoSort(k, rowConditions)
	col := topoSort(k, colConditions)
	if row == nil || col == nil {
		return nil
	}
	pos := make([]int, k)
	for i, v := range col {
		pos[v] = i
	}
	ans := make([][]int, k)
	for i, x := range row {
		ans[i] = make([]int, k)
		ans[i][pos[x]] = x + 1
	}
	return ans
}

java 解法, 执行用时: 10 ms, 内存消耗: 53.3 MB, 提交时间: 2023-06-26 09:56:56

class Solution {
    int[] topoSort(int k, int[][] edges) {
        List<Integer>[] g = new ArrayList[k];
        Arrays.setAll(g, e -> new ArrayList<>());
        var inDeg = new int[k];
        for (var e : edges) {
            int x = e[0] - 1, y = e[1] - 1; // 顶点编号从 0 开始，方便计算
            g[x].add(y);
            ++inDeg[y];
        }

        var order = new ArrayList<Integer>();
        var q = new ArrayDeque<Integer>();
        for (var i = 0; i < k; ++i)
            if (inDeg[i] == 0) q.push(i);
        while (!q.isEmpty()) {
            var x = q.pop();
            order.add(x);
            for (var y : g[x])
                if (--inDeg[y] == 0) q.push(y);
        }
        return order.stream().mapToInt(x -> x).toArray();
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] row = topoSort(k, rowConditions), col = topoSort(k, colConditions);
        if (row.length < k || col.length < k) return new int[][]{};
        var pos = new int[k];
        for (var i = 0; i < k; ++i)
            pos[col[i]] = i;
        var ans = new int[k][k];
        for (var i = 0; i < k; ++i)
            ans[i][pos[row[i]]] = row[i] + 1;
        return ans;
    }
}

python3 解法, 执行用时: 88 ms, 内存消耗: 22.8 MB, 提交时间: 2023-06-26 09:56:36

# 拓扑排序
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo_sort(edges: List[List[int]]) -> List[int]:
            g = [[] for _ in range(k)]
            in_deg = [0] * k
            for x, y in edges:
                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算
                in_deg[y - 1] += 1
            order = []
            q = deque(i for i, d in enumerate(in_deg) if d == 0)
            while q:
                x = q.popleft()
                order.append(x)
                for y in g[x]:
                    in_deg[y] -= 1
                    if in_deg[y] == 0:
                        q.append(y)
            return order if len(order) == k else None

        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:
            return []
        pos = {x: i for i, x in enumerate(col)}
        ans = [[0] * k for _ in range(k)]
        for i, x in enumerate(row):
            ans[i][pos[x]] = x + 1
        return ans