首页 > 代码库 > 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.
/** * 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) //size is less then or equal to 2 then just return size return points.size(); unordered_map<string, int> dupMap; for(int i = 0; i < points.size(); i++){ // delete dubs and keep track of their count in dupMap string pt = to_string(points[i].x) + ‘ ‘+ to_string(points[i].y); if(dupMap.count(pt) == 0) dupMap[pt] = 0; else{ dupMap[pt]++; points.erase(points.begin() + i--); } } if(points.size() == 1){ //if every item was a dup string pt = to_string(points[0].x) + ‘ ‘+ to_string(points[0].y); return dupMap[pt] + 1; } int max = 2; for(int i = 0; i < points.size()-1; i++){//O(N^2) calclate every combination of points unordered_map<string, int> hashMap; string pt = to_string(points[i].x) +‘ ‘+ to_string(points[i].y); for(int j = i+1; j < points.size(); j++){ string pt2 = to_string(points[j].x) +‘ ‘+ to_string(points[j].y); string eq = ""; if(points[i].x == points[j].x) eq = "x = " + to_string(points[i].x); //infinte slope else{ float m = (float)(points[j].y - points[i].y) / (float)(points[j].x - points[i].x);//slope m = (m < 0.0005 && m > -0.0005)? 0: m; //rounding to 0 for floats float b = (float)points[i].y - (float)(m * points[i].x); eq = "y =" + to_string(m) + ‘+‘ + to_string(b); //form equation string } if(hashMap.count(eq) == 0){ //havent seen this eq before hashMap[eq] = 2; if(dupMap[pt] > 0) //pt has dupes hashMap[eq] += dupMap[pt]; if(dupMap[pt2] > 0)//pt2 has dupes hashMap[eq] += dupMap[pt2]; } else hashMap[eq] += (dupMap[pt2] > 0)? dupMap[pt2] + 1 : 1; max = (hashMap[eq] > max)? hashMap[eq] : max; } } return max; //return the max count }};
Max Points on a Line
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。