题目链接：Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

这道题的要求是统计二维平面上最多有多少点在同一直线上。

这是一道数学的问题，而且是计算几何，直接的思路是：这n个点总共构成n*(n-1)/2条直线，然后对每条直线检测是有多少点在这条直线上，返回最大的数值。不过这样的时间复杂度为O(n^3)。

另一种思路，依次固定每一个点，然后寻找与该点共线的点最多有多少个。而在寻找共线点的时候，可以用Hash记录线的斜率。这里只需要考虑斜率而不用考虑截距是因为所有点都是对应于一个预先固定的点构成的直线，只要斜率相同就必然在同一直线上。这样，时间复杂度为O(n^2)，空间复杂度为O(n)。

时间复杂度：O(n2)

空间复杂度：O(n)

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
41
42
43
44
45
46
47
48
49

class Solution
{
public:
    int maxPoints(vector<Point> &points)
    {
        if(points.size() == 0)
            return 0;
        
        int res = 1;
        for(int i = 0; i < points.size(); ++ i)
        {
            // key：斜率；value：点的数量
            unordered_map<double, int> map;
            int r = 0; // 用于统计与points[i]重复点的数量
            for(int j = i + 1; j < points.size(); ++ j)
            {
                // 处理点重复的情况
                if(points[i].x == points[j].x && points[i].y == points[j].y)
                {
                    ++ r;
                    continue;
                }
                // 计算points[i]和point[j]点构成直线的斜率
                double slope = calcSlope(points[i], points[j]);
                if(map.find(slope) != map.end())
                    ++ map[slope];  // 如果斜率在map中存在，对应value加1
                else
                    map[slope] = 2; // 如果斜率在map中不存在，对应value赋值为2
            }
            
            int cur = 1;// 用于统计map中的value的最大值
            // 统计map中的value的最大值
            for(auto it = map.begin(); it != map.end(); ++ it)
                cur = max(cur, it -> second);
            // 最后应该加上重复点的数量r，再与res进行比较
            res = max(res, cur + r);
        }
        return res;
    }
private:
    // 计算a点和b点构成直线的斜率
    double calcSlope(Point &a, Point &b)
    {
        if(a.x == b.x)
            return INT_MAX; // 如果斜率不存在，返回int的最大值
        else
            return (double)(a.y - b.y) / (a.x - b.x);
    }
};