首页 > 代码库 > [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; } } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。