Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1st (7 tries)
class Solution { public: int maxPoints(vector<Point> &points) { unordered_map<float,int> kmap; int maxres = 0; for(int i = 0;i < points.size();i++) { int same_num = 1; kmap.clear(); kmap[INT_MIN] = 0; for(int j = 0;j < points.size();j++) { if (j == i) continue; if (points[i].x == points[j].x && points[i].y == points[j].y) { same_num ++ ; continue; } float k = points[i].x == points[j].x?INT_MAX:(float)(points[j].y - points[i].y)/(points[j].x - points[i].x); kmap[k]++; } unordered_map<float,int>::iterator iter; for(iter = kmap.begin();iter != kmap.end();++iter) { if(iter->second+same_num>maxres) { maxres = iter->second+same_num; } } } return maxres; } };
2nd ( 4 tires)
/** * 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 max_p = 0; for(unsigned i = 0;i < points.size();i++) { map<double,int> slopes; int min_p = 0; for(unsigned j = 0;j < points.size();j++) { if(points[i].x == points[j].x && points[i].y == points[j].y) { min_p++; continue; } double k = (points[i].x - points[j].x)?( (double)(points[i].y - points[j].y) )/(points[i].x - points[j].x):INT_MAX; if(slopes.find(k) == slopes.end()) slopes[k] = 1; else slopes[k]++; } if(slopes.size() == 0) { if(min_p > max_p) max_p = min_p; } else { for(map<double,int>::iterator iter = slopes.begin();iter != slopes.end();++iter) { if(iter->second + min_p > max_p) max_p = iter->second + min_p; } } } return max_p; } };
【Leetcode】Max Points on a Line,布布扣,bubuko.com
【Leetcode】Max Points on a Line
原文:http://www.cnblogs.com/weixliu/p/3924368.html