Lint Code——最多共线的点的个数
2024-08-26 04:32:27
题目链接：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=;
if(points.size()==){
return num;
}
num=; Point point_i,point_j;
double k; for(int i=;i<points.size();i++){
point_i=points[i];
int same=;
map<double,int> res;
map<double ,int >::iterator it;
for(int j=i+;j<points.size();j++){
point_j=points[j];
if(point_j.x-point_i.x == && point_j.y-point_i.y == ){//同一点
same++;
}else if(point_j.x-point_i.x == && point_j.y-point_i.y !=){
k=(numeric_limits<double>::max)();
if(check(res,k)){
it=res.find(k);
it->second++;
}else {
res.insert(pair<double,int>(k,));
}
}else if(point_j.x-point_i.x != ){
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,));
}
}
}
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;
}
};
最新文章
- 扩大ubuntu虚拟机硬盘空间
- ASP.NET Web API 安全筛选器
- HDU 3374 最小/大表示法+KMP
- Visual C++ 中的重大更改
- JS设计模式一：单例模式
- I.MX6 SHT20 Linux 驱动移植
- jenkins：应用篇（Gatling plugin的使用）
- 如何判断TCP包是否发送成功
- phper 要求
- mydumper工作原理， seconds_behind_master的陷阱和pt-heartbeat （102)
- Android 常用系统控件
- 3D objects key rendering steps
- Maven POM配置释疑
- Android: Type Method 'NewStringUTF' could not be resolved
- USACO Section 1.1-2 Greedy Gift Givers
- mysql-高性能索引策略
- servlet中 java.lang.ClassNotFoundException: com.mysql.jdbc.Driver异常
- 关于H5的一些杂思细想（一）
- python文件读和写
- 使用Nginx部署静态网站