首页 > 代码库 > 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.
此题是求直线上点最多的点数，
根据两点构成一条直线，在同一条直线上，任意两点之间的斜率都相同，故需要对每个点遍历一遍，
假设遍历点为k，则过k的所有直线上点数最多的点能被求出（通过其他点到点k得斜率判断，如果斜率相等，则在同一条直线上），
然后取最大值即可。
注意本题要考虑相同点得处理，以及斜率无穷大的处理，
相同点得处理，只需要记录相同点数即可
斜率无穷大得处理，只需要记斜率为INT_MAX即可
代码用到了unordered_map，即哈希表，存取时间复杂度为O(1)
本题的整体复杂度为O(n*n)
int maxPoints(vector<Point> &points){ if(points.size() <= 2) return points.size(); int maxCnt = 1; for(int i = 0 ; i < points.size(); ++ i){ int dup = 0; unordered_map<double,int> kmap; kmap.insert(make_pair(INT_MIN,1)); for(int j = i + 1; j < points.size(); ++ j){ if(points[j].x == points[i].x && points[j].y == points[i].y) dup++; else{ double k = points[j].x-points[i].x == 0 ? INT_MAX:(double)(points[j].y - points[i].y)/(double)(points[j].x - points[i].x); if(kmap.find(k)!=kmap.end()) kmap[k]++; else kmap.insert(make_pair(k,2)); } } for(unordered_map<double,int>::iterator iter = kmap.begin(); iter!=kmap.end(); ++ iter){ if(iter->second+dup > maxCnt) maxCnt = iter->second+dup; } } return maxCnt;}
本题的改进型可以为3D平面，求出在同一个平面上最多的点数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。