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

[LeetCode] 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.

思路:

(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;
    }
    }
};