LeetCode149—Max Points on a Line

￡神魔★判官ぃ 2022-07-15 09:21 101阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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轴的点。

最后最大值可能有两种情况：  
1. 与点p重合的点 + 与点p斜率相同  
2. 与点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;//包含本身
        }
    };

[Link 1]: https://leetcode.com/problems/max-points-on-a-line/