Max Points on a Line--LeetCode

旧城等待， 2022-08-07 13:35 146阅读 0赞

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

思路：二维坐标上的点，最多的共线的点数。

共线：要么是垂直X轴，要么垂直与Y轴，要么就是斜线，一个坐标点，按照X排序，比较垂直与X轴的最多的点，按照Y轴排序，比较垂直Y轴的最多的点。

至于怎么看斜线。

任意一条直线都可以表述为

y = ax + b

假设，有两个点(x1,y1), (x2,y2)，如果他们都在这条直线上则有

y1 = kx1 +b

y2 = kx2 +b

由此可以得到关系，k = (y2-y1)/(x2-x1)。即如果点c和点a的斜率为k, 而点b和点a的斜率也为k，可以知道点c和点b也在一条线上。

取定一个点points\[i\], 遍历其他所有节点, 然后统计斜率相同的点数，并求取最大值即可

对于任意一个点，和其他任意不同的点存在斜线斜率，看某个斜率的个数，然后对所有的点都这样操作，最后找到最多的点数。

int maxPoints(vector<pair<int,int> > &points)
    {
        if(points.size() <=2)
         return points.size();
        int maxnum=0;
        double temp,X,Y;
        int i,j,same;
        
        sort(points.begin(),points.end(),compY);
        for(i=0;i<points.size();)
        {
           for(j=i+1;j<points.size();j++)
               if(points[j].second != points[i].second)
               {
                  maxnum = max(maxnum,j-i);
                  break;
               }                  
           i = j;               
        }
        sort(points.begin(),points.end(),compX);
        for(i=0;i<points.size();)
        {
           for(j=i+1;j<points.size();j++)
               if(points[j].first != points[i].first)
               {
                     maxnum = max(maxnum,j-i);   
                     break;
               }                
           i = j;               
        }
         if(points[points.size()-1].first -points[0].first < maxnum)
         return maxnum;
        for(i=0;i<points.size();i++)
        {
          same =1;
          map<double,int> flip;
          flip.clear();
          for(j=0;j<points.size();j++)
          {
              if(i == j)
               continue;
              if(points[i].first==points[j].first&&points[i].second==points[j].second)
              {
                 same++;
                 continue;
              } 
              if(points[i].first != points[j].first && points[i].second != points[j].second)
              {
                 X= points[i].first - points[j].first;
                 Y= points[i].second- points[j].second;
                 temp = X/Y;
                 flip[temp]++; 
                  
              }     
          }
          map<double,int>::iterator it = flip.begin();  
          for(; it != flip.end(); it++)  
                if(it->second + same > maxnum)  
                    maxnum = it->second + same;                               
        }
         return maxnum;
            
    }

ps:其实题目的思路非常的简单，我们需要求共线的点数，那么任意两点都可以构成一条子线，这条直线的要么垂直X轴，要么垂直Y轴，要么有斜率，那么可以飞卫这三种情况，我们可以使用map来记录斜率和对应的斜率的个数，就可以知道共线的点数了。

其实根据前面的代码，这道题目并不是非常的好，首先没必要排序，二者也没必要非三种情况，两种特殊的情况，一种斜率为0，一种斜率为无穷大，都可以在map中体现出来，同时为了避免求斜率时点重复，可以使用两层循环，

for(int i =0;i<size;i++)

for(int j = i;j<size ;j++)

这样的两层循环就避免了重复求斜率的问题