Question

2392. 给定条件下构造矩阵

English Version

题目描述

给你一个 正 整数 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]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 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 <= 104
• rowConditions[i].length == colConditions[i].length == 2
• 1 <= abovei, belowi, lefti, righti <= k
• abovei != belowi
• lefti != righti

解法

方法一：拓扑排序

利用拓扑排序，找到一个合法的 row 序列和 col 序列，然后根据这两个序列构造出矩阵。

时间复杂度 $O(m+n+k)$。其中 $m$ 和 $n$ 分别为 rowConditions 和 colConditions 的长度，而 $k$ 为题目中给定的正整数。

class Solution:
  def buildMatrix(
    self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]
  ) -> List[List[int]]:
    def f(cond):
      g = defaultdict(list)
      indeg = [0] * (k + 1)
      for a, b in cond:
        g[a].append(b)
        indeg[b] += 1
      q = deque([i for i, v in enumerate(indeg[1:], 1) if v == 0])
      res = []
      while q:
        for _ in range(len(q)):
          i = q.popleft()
          res.append(i)
          for j in g[i]:
            indeg[j] -= 1
            if indeg[j] == 0:
              q.append(j)
      return None if len(res) != k else res

    row = f(rowConditions)
    col = f(colConditions)
    if row is None or col is None:
      return []
    ans = [[0] * k for _ in range(k)]
    m = [0] * (k + 1)
    for i, v in enumerate(col):
      m[v] = i
    for i, v in enumerate(row):
      ans[i][m[v]] = v
    return ans

class Solution {
  private int k;

  public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
    this.k = k;
    List<Integer> row = f(rowConditions);
    List<Integer> col = f(colConditions);
    if (row == null || col == null) {
      return new int[0][0];
    }
    int[][] ans = new int[k][k];
    int[] m = new int[k + 1];
    for (int i = 0; i < k; ++i) {
      m[col.get(i)] = i;
    }
    for (int i = 0; i < k; ++i) {
      ans[i][m[row.get(i)]] = row.get(i);
    }
    return ans;
  }

  private List<Integer> f(int[][] cond) {
    List<Integer>[] g = new List[k + 1];
    Arrays.setAll(g, key -> new ArrayList<>());
    int[] indeg = new int[k + 1];
    for (var e : cond) {
      int a = e[0], b = e[1];
      g[a].add(b);
      ++indeg[b];
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 1; i < indeg.length; ++i) {
      if (indeg[i] == 0) {
        q.offer(i);
      }
    }
    List<Integer> res = new ArrayList<>();
    while (!q.isEmpty()) {
      for (int n = q.size(); n > 0; --n) {
        int i = q.pollFirst();
        res.add(i);
        for (int j : g[i]) {
          if (--indeg[j] == 0) {
            q.offer(j);
          }
        }
      }
    }
    return res.size() == k ? res : null;
  }
}

class Solution {
public:
  int k;

  vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
    this->k = k;
    auto row = f(rowConditions);
    auto col = f(colConditions);
    if (row.empty() || col.empty()) return {};
    vector<vector<int>> ans(k, vector<int>(k));
    vector<int> m(k + 1);
    for (int i = 0; i < k; ++i) {
      m[col[i]] = i;
    }
    for (int i = 0; i < k; ++i) {
      ans[i][m[row[i]]] = row[i];
    }
    return ans;
  }

  vector<int> f(vector<vector<int>>& cond) {
    vector<vector<int>> g(k + 1);
    vector<int> indeg(k + 1);
    for (auto& e : cond) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      ++indeg[b];
    }
    queue<int> q;
    for (int i = 1; i < k + 1; ++i) {
      if (!indeg[i]) {
        q.push(i);
      }
    }
    vector<int> res;
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        int i = q.front();
        res.push_back(i);
        q.pop();
        for (int j : g[i]) {
          if (--indeg[j] == 0) {
            q.push(j);
          }
        }
      }
    }
    return res.size() == k ? res : vector<int>();
  }
};

func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
  f := func(cond [][]int) []int {
    g := make([][]int, k+1)
    indeg := make([]int, k+1)
    for _, e := range cond {
      a, b := e[0], e[1]
      g[a] = append(g[a], b)
      indeg[b]++
    }
    q := []int{}
    for i, v := range indeg[1:] {
      if v == 0 {
        q = append(q, i+1)
      }
    }
    res := []int{}
    for len(q) > 0 {
      for n := len(q); n > 0; n-- {
        i := q[0]
        q = q[1:]
        res = append(res, i)
        for _, j := range g[i] {
          indeg[j]--
          if indeg[j] == 0 {
            q = append(q, j)
          }
        }
      }
    }
    if len(res) == k {
      return res
    }
    return []int{}
  }

  row := f(rowConditions)
  col := f(colConditions)
  if len(row) == 0 || len(col) == 0 {
    return [][]int{}
  }
  m := make([]int, k+1)
  for i, v := range col {
    m[v] = i
  }
  ans := make([][]int, k)
  for i := range ans {
    ans[i] = make([]int, k)
  }
  for i, v := range row {
    ans[i][m[v]] = v
  }
  return ans
}

function buildMatrix(k: number, rowConditions: number[][], colConditions: number[][]): number[][] {
  function f(cond) {
    const g = Array.from({ length: k + 1 }, () => []);
    const indeg = new Array(k + 1).fill(0);
    for (const [a, b] of cond) {
      g[a].push(b);
      ++indeg[b];
    }
    const q = [];
    for (let i = 1; i < indeg.length; ++i) {
      if (indeg[i] == 0) {
        q.push(i);
      }
    }
    const res = [];
    while (q.length) {
      for (let n = q.length; n; --n) {
        const i = q.shift();
        res.push(i);
        for (const j of g[i]) {
          if (--indeg[j] == 0) {
            q.push(j);
          }
        }
      }
    }
    return res.length == k ? res : [];
  }

  const row = f(rowConditions);
  const col = f(colConditions);
  if (!row.length || !col.length) return [];
  const ans = Array.from({ length: k }, () => new Array(k).fill(0));
  const m = new Array(k + 1).fill(0);
  for (let i = 0; i < k; ++i) {
    m[col[i]] = i;
  }
  for (let i = 0; i < k; ++i) {
    ans[i][m[row[i]]] = row[i];
  }
  return ans;
}