首页 > 代码库 > 【LeetCode】Max Points on a Line
【LeetCode】Max Points on a Line
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.
点和方向确定一条直线。
需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。
a和b如果不重合，就可以确定一条直线。
对于每个点a，构建 斜率->点数 的map。
(1)b与a重合，以a起始的所有直线点数+1
(2)b与a不重合，a与b确定的直线点数+1
/** * Definition for a point. * 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) { if(points.size() < 2) return points.size(); int maxp = 0; for(vector<Point>::size_type st1 = 0; st1 < points.size(); st1 ++) { Point p1 = points[st1]; map<double, int> lineCount; //以points[st1]为端点，以ygap/xgap为斜率的直线上有多少个点 int curmax = 1; int dup = 0; for(vector<Point>::size_type st2 = st1+1; st2 < points.size(); st2 ++) { Point p2 = points[st2]; int xgap = p1.x - p2.x; int ygap = p1.y - p2.y; if(xgap == 0 && ygap == 0) { dup ++; } else if(xgap == 0) { if(lineCount.find(INT_MAX) == lineCount.end()) { lineCount.insert(map<double, int>::value_type(INT_MAX, 2)); curmax = max(2, curmax); } else { lineCount[INT_MAX] ++; curmax = max(lineCount[INT_MAX], curmax); } } else { double k = ygap*1.0/xgap; if(lineCount.find(k) == lineCount.end()) { curmax = max(2, curmax); lineCount.insert(map<double, int>::value_type(k, 2)); } else { lineCount[k] ++; curmax = max(lineCount[k], curmax); } } } maxp = max(maxp, curmax+dup); } return maxp; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。