首页 > 代码库 > Max Points on a Line （HASH TABLE
Max Points on a Line （HASH TABLE
QUESTION
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1ST TRY
/** * 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) { int ret = 0; float slope; unordered_map<float, int> slopeCounter; for(int i = 0; i < points.size(); i++) { for(int j= i+1; j < points.size(); j++) { slope = (points[j].y-points[i].y)/(points[j].x-points[i].x); slopeCounter[slope]++; if(slopeCounter[slope] > ret) ret = slopeCounter[slope]; } } return ret; }};
Result: Runtime Error
Last executed input: [(0,0),(0,0)]
2ND TRY
注意了除数不能为0
class Solution {public: int maxPoints(vector<Point> &points) { if(points.empty()) return 0; int ret = 0; float slope; unordered_map<float, int> slopeCounter; int counter = 0; for(int i = 0; i < points.size(); i++) { for(int j= i+1; j < points.size(); j++) { if(points[j].x-points[i].x==0) { counter++; continue; } slope = (points[j].y-points[i].y)/(points[j].x-points[i].x); slopeCounter[slope]++; if(slopeCounter[slope] > ret) ret = slopeCounter[slope]; } } return 1+max(ret,counter); }};
Result: Wrong
Input: [(0,0),(-1,-1),(2,2)]
Output: 4
Expected: 3
3RD TRY
考虑一条直线经过的点有重复计算
class Solution {public: int maxPoints(vector<Point> &points) { if(points.empty()) return 0; int ret = 0; int tmpMax = 0; float slope; unordered_map<float, int> slopeCounter; int verticalCounter = 0; for(int i = 0; i < points.size(); i++) { for(int j= i+1; j < points.size(); j++) { if(points[j].x-points[i].x==0) verticalCounter++; else { slope = (points[j].y-points[i].y)/(points[j].x-points[i].x); slopeCounter[slope]++; } } tmpMax = verticalCounter; for(unordered_map< float,int >::iterator it=slopeCounter.begin(); it!=slopeCounter.end();it++) { tmpMax =max(tmpMax, it->second); } ret = max(ret, tmpMax); slopeCounter.clear(); //clear map, for line through point[i] is done. verticalCounter = 0; } return 1+max(ret,verticalCounter); }};
Result: Wrong
Input: [(0,0),(1,1),(0,0)]
Output: 2
Expected: 3
4TH TRY
考虑有重叠点的情况
class Solution {public: int maxPoints(vector<Point> &points) { if(points.empty()) return 0; int ret = 0; int tmpMax = 0; float slope; unordered_map<float, int> slopeCounter; int verticalCounter = 0; int repCounter = 0; int i,j; for(i = 0; i < points.size(); i++) { for(j = 0; j < i; j++) { if(points[j].x==points[i].x && points[j].y==points[i].y) break; } if(j < i) continue; for(j= i+1; j < points.size(); j++) { if(points[j].x==points[i].x && points[j].y==points[i].y) repCounter++; else if(points[j].x==points[i].x) verticalCounter++; else { slope = (float)(points[j].y-points[i].y)/(points[j].x-points[i].x); //必须要有float，否则计算结果是整数 slopeCounter[slope]++; } } tmpMax = verticalCounter; for(unordered_map< float,int >::iterator it=slopeCounter.begin(); it!=slopeCounter.end();it++) {//traverse map tmpMax =max(tmpMax, it->second); } ret = max(ret, tmpMax+repCounter); slopeCounter.clear(); //clear map, for line through point[i] is done. verticalCounter = 0; repCounter = 0; } return ret+1; }};
Result: Accepted
Max Points on a Line （HASH TABLE
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。