首页 > 代码库 > Lint Code——最多共线的点的个数
Lint Code——最多共线的点的个数
题目链接:http://www.lintcode.com/zh-cn/problem/max-points-on-a-line/#
条件:给一个点数组
目标:求出共线的点的最多个数
实现:时间复杂度——O(n^2)
要考虑的特殊情况是:①有相同点(这个也太特喵隐蔽了)②斜率不存在的点
思路:暴力求解,遍历每一个点,与他之后的点进行匹配,用一个map<double,int>存储斜率对应的个数。
代码:
/** * 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: /** * @param points an array of point * @return an integer */ bool check(map<double,int> &res,double k){ map<double ,int >::iterator it; it=res.find(k); if(it==res.end()){ return false; } return true; } void change(map<double,int> &res,double k,int &num){ map<double ,int >::iterator it; it=res.find(k); it->second++; if(it->second>num){ num=it->second; } } int maxPoints(vector<Point>& points) { // Write your code here int num=0; if(points.size()==0){ return num; } num=1; Point point_i,point_j; double k; for(int i=0;i<points.size();i++){ point_i=points[i]; int same=1; map<double,int> res; map<double ,int >::iterator it; for(int j=i+1;j<points.size();j++){ point_j=points[j]; if(point_j.x-point_i.x == 0 && point_j.y-point_i.y ==0 ){//同一点 same++; }else if(point_j.x-point_i.x == 0 && point_j.y-point_i.y !=0){ k=(numeric_limits<double>::max)(); if(check(res,k)){ it=res.find(k); it->second++; }else { res.insert(pair<double,int>(k,1)); } }else if(point_j.x-point_i.x != 0 ){ k=(point_j.y-point_i.y)*1.0/(point_j.x-point_i.x); if(check(res,k)){ it=res.find(k); it->second++; }else { res.insert(pair<double,int>(k,1)); } } } if(res.empty()){ if(same>num){ num=same; } } for(it=res.begin();it!=res.end();it++){ if(it->second+same>num){ num=it->second+same; } } } return num; } };
Lint Code——最多共线的点的个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。