Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
---------------------------------------------------------------------------------
O(n^2)
/** * 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 maxP = 2; if (points.size() == 0 || points.size() == 1) return points.size(); for (int i = 0; i < points.size(); i++) { unordered_map<double,int> slopes; int samex = 1; int samePoints = 0; int curMax = 0; for (int j = i + 1; j < points.size(); j++) { double xdistance = points[i].x - points[j].x; double ydistance = points[i].y - points[j].y; if (xdistance == 0 && ydistance == 0) { samePoints++; continue; }else if (xdistance == 0) { samex++; continue; } double slope = ydistance / xdistance; if (slopes.find(slope) == slopes.end()) { slopes[slope] = 2; }else { slopes[slope]++; } curMax = max(curMax,max(samex,slopes[slope])); } curMax = max(samex,curMax); maxP = max(maxP,curMax + samePoints); } return maxP; } };
No comments:
Post a Comment