Max Points On A Line

149. 直线上最多的点数

分析

哈希表：通过哈希表来记录每个斜率出现的频次。对于每个点，遍历其他点，计算斜率，并更新哈希表。如果多个点具有相同的斜率，则它们在同一条直线上
特殊情况：需要考虑以下几种情况：
- 重复点：如果两个点重合，它们的斜率是相同的
- 竖直线：当 dx = 0 时，说明是竖直线，斜率可以用一个特殊值（如无穷大）表示
最终结果：对于每个点，计算该点与其他点的最大共线点数，并维护一个最大值

时间复杂度

时间复杂度 O(n^2)，其中 n 是点的数量。对于每个点 p，我们遍历所有其他点 q，计算它们的斜率

空间复杂度

空间复杂度为 O(n)

C++代码

 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


class Solution
{
public:
    int maxPoints(vector<vector<int>>& points)
    {
        int res = 0;
        for (std::vector<int>& p : points)
        {
            int same = 0, vertical = 0;
            std::unordered_map<long double, int> count;
            for (std::vector<int>& q : points)
            {
                if (p == q)  // 统计重叠点的个数
                    ++same;
                else if (p[0] == q[0])  // x坐标相同，统计竖直线上点的个数
                    ++vertical;
                else
                {
                    long double slope = (long double)(q[1] - p[1]) / (q[0] - p[0]);  // 计算斜率
                    ++count[slope];  // 记录相同斜率的点数
                }
            }

            // 找到最大斜率的点数（加上重叠点数）
            for (auto [slope, cnt] : count)
                res = std::max(res, same + cnt);

            // 比较竖直线的点数（加上重叠点数）和最大斜率的点数
            res = std::max(res, same + vertical);
        }
        return res;
    }
};