Medium

题目描述

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示笛卡尔平面上第 i 个点的坐标。

水平梯形是一个凸四边形，至少有一对水平边（即平行于 x 轴）。当且仅当两条直线具有相同的斜率时，它们才平行。

返回通过从 points 中选择任意四个不同的点可以形成的唯一水平梯形的数量。

由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出：3
解释：
有三种不同的方式选择四个点形成水平梯形：
- 使用点 [1,0], [2,0], [3,2], [2,2]
- 使用点 [2,0], [3,0], [3,2], [2,2]  
- 使用点 [1,0], [3,0], [3,2], [2,2]

示例 2：

输入：points = [[0,0],[1,0],[0,1],[2,1]]
输出：1
解释：
只有一个水平梯形可以被形成。

约束条件：

  • 4 <= points.length <= 10^5
  • -10^8 <= xi, yi <= 10^8
  • 所有点都是两两不同的

提示：

  • 对于平行于 x 轴的直线，其所有点必须具有相同的 y 坐标
  • 按 y 坐标对点进行分组
  • 选择两个不同的组（两条水平线），从每组中选择两个点形成梯形

解题思路

解题思路

要形成水平梯形，我们需要至少一对平行于 x 轴的边。这意味着我们需要找到两条水平线（具有相同 y 坐标的点），然后从每条线上选择两个点。

核心思路：

  1. 按 y 坐标分组：将所有点按其 y 坐标进行分组，每个组代表一条水平线
  2. 选择两条水平线：从所有水平线中选择两条不同的线
  3. 计算组合数：对于每对水平线，如果第一条线有 m 个点，第二条线有 n 个点，那么可以形成的梯形数量为 C(m,2) × C(n,2)，其中 C(n,k) 表示从 n 个元素中选择 k 个的组合数

算法步骤：

  1. 遍历所有点，按 y 坐标分组存储
  2. 对于每个 y 坐标，记录该水平线上的点数
  3. 枚举所有可能的水平线对，计算每对能形成的梯形数量
  4. 累加所有结果并取模

这种方法的时间复杂度为 O(n + k²)，其中 n 是点的总数，k 是不同 y 坐标的数量。空间复杂度为 O(k)。

代码实现

class Solution {
public:
    int countTrapezoids(vector<vector<int>>& points) {
        const int MOD = 1e9 + 7;
        map<int, int> yCount;
        
        // 按y坐标分组计数
        for (auto& point : points) {
            yCount[point[1]]++;
        }
        
        vector<int> counts;
        for (auto& p : yCount) {
            if (p.second >= 2) {
                counts.push_back(p.second);
            }
        }
        
        long long result = 0;
        int n = counts.size();
        
        // 枚举所有可能的水平线对
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long long count1 = (long long)counts[i] * (counts[i] - 1) / 2;
                long long count2 = (long long)counts[j] * (counts[j] - 1) / 2;
                result = (result + count1 * count2) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 按y坐标分组计数
        y_count = {}
        for x, y in points:
            y_count[y] = y_count.get(y, 0) + 1
        
        # 只保留至少有2个点的水平线
        counts = [count for count in y_count.values() if count >= 2]
        
        result = 0
        n = len(counts)
        
        # 枚举所有可能的水平线对
        for i in range(n):
            for j in range(i + 1, n):
                # 计算组合数 C(counts[i], 2) * C(counts[j], 2)
                count1 = counts[i] * (counts[i] - 1) // 2
                count2 = counts[j] * (counts[j] - 1) // 2
                result = (result + count1 * count2) % MOD
        
        return result

public class Solution {
    public int CountTrapezoids(int[][] points) {
        const int MOD = 1000000007;
        var yCount = new Dictionary<int, int>();
        
        // 按y坐标分组计数
        foreach (var point in points) {
            int y = point[1];
            yCount[y] = yCount.GetValueOrDefault(y, 0) + 1;
        }
        
        var counts = new List<int>();
        foreach (var count in yCount.Values) {
            if (count >= 2) {
                counts.Add(count);
            }
        }
        
        long result = 0;
        int n = counts.Count;
        
        // 枚举所有可能的水平线对
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long count1 = (long)counts[i] * (counts[i] - 1) / 2;
                long count2 = (long)counts[j] * (counts[j] - 1) / 2;
                result = (result + count1 * count2) % MOD;
            }
        }
        
        return (int)result;
    }
}

var countTrapezoids = function(points) {
    const MOD = 1e9 + 7;
    const yCount = new Map();
    
    // 按y坐标分组计数
    for (const [x, y] of points) {
        yCount.set(y, (yCount.get(y) || 0) + 1);
    }
    
    const counts = [];
    for (const count of yCount.values()) {
        if (count >= 2) {
            counts.push(count);
        }
    }
    
    let result = 0;
    const n = counts.length;
    
    // 枚举所有可能的水平线对
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const count1 = Math.floor(counts[i] * (counts[i] - 1) / 2);
            const count2 = Math.floor(counts[j] * (counts[j] - 1) / 2);
            result = (result + count1 * count2) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + k²)，其中 n 是点的总数，k 是不同 y 坐标的数量
空间复杂度O(k)，用于存储每个 y 坐标对应的点数