LeetCode149—Max Points on a Line-蒲公英云

LeetCode149—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.

Subscribe to see which companies asked this question

分析

O(n2)复杂度，每个点都要考虑三种情况：

1.普通的点，在同一直线上满足slope=y1−y2x1−x2相等。
2.跟当前点重合的点。
3.跟当前点在同一条直线且平行于y轴的点。

最后最大值可能有两种情况：

与点p重合的点 + 与点p斜率相同
与点p重合的点 + 与点p斜率相同且平行与y轴

返回结果最后+1表示包含点p即可。

代码

class Solution {
private:
    /*计算斜率*/
    double Slope(Point&a ,Point&b)
    {
        return (b.y-a.y)*1.0/(b.x-a.x);
    }
public:
    int maxPoints(vector<Point>& points)
    {
        if(points.size()<2)
            return points.size();
        int res=0;
        for(int i=0;i<points.size();i++)
        {
            int local=0;//局部最优
            int same=0;//与当前点p重合的点
            int infinity=0;//与当前点p平行于Y轴的点
            unordered_map<double,int>count;//与当前点p斜率相同的点
            for(int j=i+1;j<points.size();j++)
            {
                if(points[i].x==points[j].x&&points[i].y==points[j].y)
                {
                    ++same;
                }
                else if(points[i].x==points[j].x)
                {
                    ++infinity;
                }
                else
                {
                    double slope= Slope(points[i],points[j]);
                    count[slope]++;
                }
            }
            int tmp=0;
            for(auto it = count.begin();it!=count.end();it++)
            {
                tmp=max(tmp,it->second);
            }
            local=max(tmp+same,same+infinity);//局部最优
            res=max(local,res);//全局最优
        }
        return res+1;//包含本身
    }
};