🔗 🟡 3128. Right Triangles 1541

tags: Biweekly Contest 129 陣列(Array) 雜湊表(Hash Table) 計數(Counting) 數學(Math) 組合數學(Combinatorics)

題意

給定一個二維 boolean 矩陣 gridgrid 。

如果 gridgrid 中 3 個元素滿足：一個元素與另一個元素在 同一橫列(row)，同時與第三個元素在 同一直行(col) ，那麼這 3 個元素稱為一個 直角三角形 。這 3 個元素互相之間不需要相鄰。

返回使用 gridgrid 中的 3 個元素可以構建的 直角三角形 數目，且滿足 3 個元素值 都 為 11 。

思路：枚舉中間點 + 乘法原理

令 row_cnt[i]row\_cnt[i] 表示 gridgrid 中第 ii 橫列(row) 中 11 的數量，col_cnt[j]col\_cnt[j] 表示 gridgrid 中第 jj 直行(col) 中 11 的數量。

則若 row[i][j]=1row[i][j] = 1，則以其作直角頂點的直角三角形數量為 (row_cnt[i]−1)×(col_cnt[j]−1)(row\_cnt[i] - 1) \times (col\_cnt[j] - 1) ，因為除了中間點外，同一橫列和直行上都只能選擇 11 個頂點。

  • 在同一橫列(row)中，可選擇的點數為 row_cnt[i]−1row\_cnt[i] - 1 （排除自身）
  • 在同一直行(col)中，可選擇的點數為 col_cnt[j]−1col\_cnt[j] - 1 （排除自身）
  • 根據乘法原理，全部的組合數為 (row_cnt[i]−1)×(col_cnt[j]−1)(row\_cnt[i] - 1) \times (col\_cnt[j] - 1)

故可以在計算完 row_cntrow\_cnt 和 col_cntcol\_cnt 後，枚舉所有頂點，計算其可能的組合數，最後將所有頂點的組合數相加即可。

複雜度分析

  • 時間複雜度：O(m×n)O(m \times n)，其中 mm 和 nn 分別是矩陣的橫列數和直行數。我們需要遍歷矩陣两次，第一次統計每行每列的 11 的數量，第二次計算每個可能的直角頂點能形成的三角形數量。
  • 空間複雜度：O(m+n)O(m+n)，用於存儲 row_cntrow\_cnt 和 col_cntcol\_cnt 陣列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row_cnt = [0] * m
        col_cnt = [0] * n
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    row_cnt[i] += 1
                    col_cnt[j] += 1
        ans = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    ans += (row_cnt[i] - 1) * (col_cnt[j] - 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
class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> row_cnt(m, 0), col_cnt(n, 0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    row_cnt[i]++;
                    col_cnt[j]++;
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    ans += (row_cnt[i] - 1) * (col_cnt[j] - 1);
                }
            }
        }
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture