首页 > 代码库 > [LeetCode] Max Points on a Line

[LeetCode] Max Points on a Line

2024-07-07 13:01:43   228人阅读

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

思路：

（1）点1到点n

        （a）以点1为参考点，求“点1”与“点2到点n”各个斜率下点的个数； （求出直线最多的点数值max1）

        （b）以点2为参考点，求“点2”与“点3到点n”各个斜率下点的个数；  （求出直线最多的点数值max2，

                  注意：（b）里的直线有可能与（a）中的某条直线重合，但由于这条直线在（b）中少了点1，则直线上点的个数

                  肯定比（a）中的直线上的点的个数少，不影响（2）中结果的判断。

           ...

         （n-1）以点n-1为参考点，求“点n-1”与“点n”斜率下点的个数；（求出直线最多的点数值maxn_1）

（2）则maxNum = max（max1，max2，maxn_1） ;

 ps：（考虑到参考点可能会有好几个点的情况）

       （考虑到垂直时的情况）

 

 

注意事项：

（1） （0，0）（0，0）点算是两个点；

（2）  注意斜率k计算过程中，虽然k声明为double型，但如果被除数和除数都是整形的话，k也会退化为int型，导致结果不正确。

（3）其他注意事项见程序注释部分，写的很详细。

 

 

 
 struct Point {
      int x;
      int y;
      Point() : x(0), y(0) {}
      Point(int a, int b) : x(a), y(b) {}
  };
 
class Solution { 
public:
    int maxPoints(vector<Point> &points) {

        int maxNum = 0;
        for(vector<Point>::iterator iter=points.begin();iter != points.end();iter++)
        {
            int numOfVerticle=1;//参考点算1个，所以初始值是1不能是0；
            double k;
            map<double,int> numOfALine;
            
            int numOfRef = 1; 

           for(vector<Point>::iterator iter1 = iter+1;iter1 != points.end();iter1++ )
           {
             if(iter->x == iter1->x)
             {
                numOfVerticle++;      //已经添加了参考点的个数
                if(iter->y == iter1->y)
                    numOfRef++;     //设置参考点的个数，参考点有可能有相同的其他几个点，比如（0，0），（0，0）算作不同的2个点
             }
             else
             {
                k = 1.0*(iter1->y - iter->y)/(iter1->x - iter->x);//一定要乘以1.0，否则k=2.9也会当作k = 2处理。或者把被除数强制转换为double
                                                                  //即  k = double(iter1->y - iter->y)/(iter1->x - iter->x)；
                ++numOfALine[k];   //注意此处没有添加参考点的个数；
             }
           }       
           
           for(map<double,int>::iterator iter2 = numOfALine.begin();iter2 != numOfALine.end();iter2++)
           {
               if(maxNum < (iter2->second+numOfRef))//注意iter2统计的是以（*iter）为参考点，不同斜率的点数，所以要加上参考点的个数；
                   maxNum = (iter2->second+numOfRef);
           
           }
           if(maxNum<numOfVerticle)
               maxNum = numOfVerticle;
        
        }
        return maxNum;  
    }
};

 下面这是以前写的，考虑的更加严谨，参考一下：

class Solution {
public:
    int maxPoints(vector<Point> &points) 
    {
        if(points.size()==0)
            return 0;
        else if(points.size()==1)
            return 1;
        else
        {
        map<double,int>slope_count;
    
        int res=1;
        for(vector<Point>::iterator iter=points.begin();iter!=points.end();iter++)
        {
            int same_count(0),vertical_count(0);
            slope_count.clear();
            for(vector<Point>::iterator iter1=iter+1;iter1!=points.end();iter1++)
            {
                if(iter->x==iter1->x)
                    {
                        if(iter->y == iter1->y)
                        same_count++;
                        else
                        vertical_count++;
                    }
                else
                    {
                        double slope=1.0*(iter->y - iter1->y)/(iter->x-iter1->x);
                        ++slope_count[slope];
                    }
            }
            res=(res>(same_count+vertical_count+1)?res:(same_count+vertical_count+1));
            for(map<double,int>::iterator itera=slope_count.begin();itera!=slope_count.end();itera++)
                res=(res > (itera->second+same_count+1)) ? res : (itera->second+same_count+1);
        }
        return res;
    }
    }
};

 


联系
我们