🔗 🔴 2392. Build a Matrix With Conditions 1961

tags: Weekly Contest 308 陣列(Array) 矩陣(Matrix) 圖(Graph) 拓樸排序(Topological Sort)

題意

給定一個正整數 kk，你需要建立一個大小為 k×kk \times k 的矩陣，使得 11 到 kk 的每個數字恰好出現一次。剩下的格子應該填入 00。

另外給定一個大小為 nn 的二維整數陣列 rowConditions\text{rowConditions}，其中 rowConditions[i]=[abovei,belowi]\text{rowConditions}[i] = [\text{above}_i, \text{below}_i]，以及一個大小為 mm 的二維整數陣列 colConditions\text{colConditions}，其中 colConditions[i]=[lefti,righti]\text{colConditions}[i] = [\text{left}_i, \text{right}_i]。這兩個陣列的元素都是從 11 到 kk 的整數。

建立的矩陣必須滿足以下條件：

  • 對於所有 00 到 n−1n - 1 之間的下標 ii，數字 abovei\text{above}_i 必須出現在比 belowi\text{below}_i 的數字所在row更上面的row中。
  • 對於所有 00 到 m−1m - 1 之間的下標 ii，數字 lefti\text{left}_i 必須出現在比 righti\text{right}_i 的數字所在column更左邊的column中。

返回任何符合條件的矩陣。如果沒有解，則返回一個空矩陣。

思路：拓樸排序(Topological Sort)

首先注意到，限制條件只存在於 row 和 row 之間，或是 column 和 column 之間，因此 [1,k][1, k] 之間的數字之間在 row 中的排序和在 column 中的排序是獨立的，可以分別考慮。

而兩個條件之間的關係可以用 有向圖(Directed Graph) 來表示，對於條件 [x,y][x, y]，表示 xx 必須在 yy 之前。因此，我們可以對 row 和 column 分別建立有向圖，然後進行 拓樸排序(Topological Sorting) ，得到每個數字在兩種限制條件下的順序。令拓樸排序的結果為 orderorder，則 order[i]order[i] 代表「第 ii 個元素是 xx」，再將其轉換為 pos[x]pos[x]，即「xx 在第 ii 個位置」。

最後，我們可以得到 xx 應該出現在第 ii 橫列和第 jj 直行，即 ans[i][j]=xans[i][j] = x，除此之外的位置填 00。

具體步驟如下：

  1. 構建有向圖：

    • 將 rowConditions\text{rowConditions} 和 colConditions\text{colConditions} 分別轉換為有向圖，其中節點代表數字，邊代表條件約束。
    • 對於每個 rowConditions[i]=[abovei,belowi]\text{rowConditions}[i] = [\text{above}_i, \text{below}_i]，我們在有向圖中添加一條從 abovei\text{above}_i 指向 belowi\text{below}_i 的邊，表示 abovei\text{above}_i 必須在 belowi\text{below}_i 的上方。
    • 對於每個 colConditions[i]=[lefti,righti]\text{colConditions}[i] = [\text{left}_i, \text{right}_i]，我們在有向圖中添加一條從 lefti\text{left}_i 指向 righti\text{right}_i 的邊，表示 lefti\text{left}_i 必須在 righti\text{right}_i 的左邊。

  2. 拓樸排序：

    • 對於 rowConditions\text{rowConditions} 和 colConditions\text{colConditions} 分別進行拓樸排序。如果存在循環（即拓樸排序無法完成），則表示無法滿足條件，返回一個空的陣列。
    • 拓樸排序的結果表示數字的相對位置。例如，對於行條件的拓樸排序結果 rowrow，row[i]row[i] 表示數字 i+1i+1 應該出現在矩陣的第 row[i]row[i] 行。

  3. 構建矩陣：

    • 使用拓樸排序的結果來填充矩陣。對於每個數字 xx，將其放置在由 row[x−1]row[x-1] 行和 col[x−1]col[x-1] 列交叉的位置。

這樣，我們就能得到一個滿足所有條件的矩陣。

複雜度分析

  • 時間複雜度：O(n+m+k2)\mathcal{O}(n + m + k^2)，其中 nn 和 mm 分別是 rowConditions\text{rowConditions} 和 colConditions\text{colConditions} 的長度，kk 是矩陣的長度。
    • 構建有向圖的時間複雜度為 O(n+m)O(n + m)。
    • 拓樸排序的時間複雜度為 O(k+E)O(k + E)，其中 EE 是邊的數量，本題中為 O(n)O(n) 和 O(m)O(m)。
    • 構建矩陣的時間複雜度為 O(k2)O(k^2)。
  • 空間複雜度：O(n+m+k)\mathcal{O}(n + m + k)，忽略答案的空間複雜度。
    • 拓樸排序的空間複雜度為 O(k+E)O(k + E)，其中 EE 是邊的數量，本題中為 O(n)O(n) 和 O(m)O(m)。
    • 用來保存拓樸排序結果的空間複雜度為 O(k)O(k)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo_sort(conditions: List[List[int]]) -> List[int]:
            g = [[] for _ in range(k)] # adjacency list
            deg = [0] * k # in-degree
            for x, y in conditions: # x 必須在 y 之前
                g[x - 1].append(y - 1)
                deg[y - 1] += 1
            order = [] # 拓樸排序的結果，第 i 個元素是 x
            q = deque(i for i, d in enumerate(deg) if d == 0)
            while q:
                x = q.popleft()
                order.append(x)
                for y in g[x]:
                    deg[y] -= 1
                    if deg[y] == 0:
                        q.append(y)
            pos = [0] * k # 把「第 i 個元素是 x」轉換為「x 在第 i 個位置」
            for i, x in enumerate(order):
                pos[x] = i
            return pos if len(order) == k else []
        row, col = topo_sort(rowConditions), topo_sort(colConditions)
        if not row or not col:
            return []
        ans = [[0] * k for _ in range(k)]
        for x, (i, j) in enumerate(zip(row, col)): # x 在第 i 橫列，第 j 直行
            ans[i][j] = x + 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> row, col;
        row = topological_sort(k, rowConditions);
        col = topological_sort(k, colConditions);
        if (row.empty() || col.empty()) return {};
        vector<vector<int>> ans(k, vector<int>(k, 0));
        for (int x = 0; x < k; x++) { // x 在第 i 橫列，第 j 直行
            ans[row[x]][col[x]] = x + 1;
        }
        return ans;
    }
    vector<int> topological_sort(int k, vector<vector<int>>& conditions) {
        vector<vector<int>> g(k); // adjacency list
        vector<int> deg(k); // in-degree
        for (auto &e : conditions) {
            int x = e[0], y = e[1];
            g[x - 1].push_back(y - 1);
            deg[y - 1]++;
        }
        vector<int> order; // 拓樸排序的結果，第 i 個元素是 x
        deque<int> q;
        for (int i = 0; i < k; i++) {
            if (deg[i] == 0) q.push_back(i);
        }
        while (!q.empty()) {
            int x = q.front(); q.pop_front();
            order.push_back(x);
            for (int y : g[x]) {
                deg[y]--;
                if (deg[y] == 0) q.push_back(y);
            }
        }
        if (order.size() != k) return {};
        vector<int> pos(k); // 把「第 i 個元素是 x」轉換為「x 在第 i 個位置」
        for (int i = 0; i < k; i++) pos[order[i]] = i;
        return pos;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl