3623. 統計梯形的數量

思路

題目要求兩條邊都平行於x軸，因此只要相同y值下有幾個點，用乘法原理算出最後有幾種梯形即可。

程式碼

哈希表

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> umap; // 記錄在同樣的 y 座標下, 有多少點。
        for(auto& p : points) {
            ++umap[p[1]];
        }
        long long res = 0, sum = 0;
        for(auto& [_, val] : umap) {
            long long k = 1LL * val * (val - 1) / 2; // 同樣的 y 座標選出兩個, 共有幾種選法
            // 選出來的兩個點, 每個都可以跟「其他同 y 座標的點」配對，只能跟已經遍歷過的配，
            // 沒遍歷過的會在遍歷到它時算到
            res += sum * k; 
            sum += k;
        }
        return res % MOD;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$