首页 > 代码库 > 【Leetcode】Max Points on a Line
【Leetcode】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.
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; }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。