max_points_on_a_line
程序员文章站
2022-06-02 22:13:46
...
/**
* Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
首先想到的是 k=(y2-y1)/(x2-x1),先锁定两个点x1,x2确定一条直线,每次进来一个点就分别与x1,x2根据上式计算斜率,比较与原来的斜率是否相等,若是就把当前直线上点数加一,然后代码大概是这样
class Solution {
public:
int maxPoints(vector<Point> &points) {
int l=points.size();
if(l==1)
return 1;
int max=0;
for(int i=0;i<l-1;i++){
for(int j=i+1;j<l;j++){
int temp=2;
float k=((float)points[i].y-(float)points[j].y)/(points[i].x-points[j].x);
for(int t=j+1;t<l;t++){
cout<<points[i].x-points[t].x<<endl;
float kn=((float)points[i].y-(float)points[t].y)/(points[i].x-points[t].x);
//cout<<kn<<endl;
// float k1=((float)points[t].y-(float)points[i].y)*(points[j].x-points[i].x);
// float k2=((float)points[j].y-(float)points[i].y)*(points[t].x-points[i].x);
if(k==kn){
//cout<<kn<<endl;
temp+=1;}
}
max=max>temp?max:temp;
}
}
return max;
}
};
这么写存在的问题是首先会有除以0的情况(一条与y轴平行的线上的点),虽然把结果转成float保存,代码不会报错(float型有表示这类数的方法),但当点一样的时候,就会出问题了。
如
(0,0)
(1,1)
(0,0)
按照公式 (0,0)(1,1) 1(斜率)
(0,0)(0,0) nan(斜率)
结果是只有两个点(但是需要是3个点)。
遇到这种情况,立马想到是除以0导致的,于是决定换一个没有除以0的公式。
(x2-x1)(y3-y1)==(x3-x1)(y2-y1)
代码与上一个类似。
但是,又有新的问题
测试用例:
[(0,9),(138,429),(115,359),(115,359),
(-30,-102),(230,709),(-150,-686),(-135,-613),
(-60,-248),(-161,-481),(207,639),(23,79),
(-230,-691),(-115,-341),(92,289),(60,336),
(-105,-467),(135,701),(-90,-394),(-184,-551),(150,774)]
对应输出应该为:
12
你的输出为:
19
当时想不太明白为什么会多算点,而且输入看上去有点复杂,于是画了图寻找这一个输入序列的特殊之处,但是没有发现什么特别的地方。
只能看自己的代码了,把代码里输出max的地方的点值都打印出来,发现求出19的地方,前两个点是一样的点,再看一下输入序列,发现有两个一样的点,再回头看公式发现问题所在。
(139,139) (139,139) (140,140) (141,141)
直接把值套进去,发现不在一条线上的点,划分到了一条线上。
对于坐标值相同的点应该特殊处理:
对于进入当前直线的第二个点(直线还没有确定),应该首先判断是否与第一个点相同,如果相同做不同的处理。
int l=points.size();
// cout<<l<<endl;
if(l==1)
return 1;
int max=0;
bool flag=false; //标记点是否一样
int repeatcount=0; //标记重复点的个数
for(int i=0;i<l-1;i++){
for(int j=i+1;j<l;j++){
// cout<<i<<" "<<j<<" "<<l<<endl;
int temp=2;
flag=false;
if((points[j].y==points[i].y) &&(points[j].x==points[i].x)){
//因为公式是基于 i,j点计算的,所以只需要计算这两个点是否重复既可以
//repeatcount+=1;
flag=true;
temp=1;
// temp=1;
// max=max>temp?max:temp;
repeatcount+=1;
temp+=repeatcount;
}
//int k=((float)points[i].y-(float)points[j].y)/(points[i].x-points[j].x);
if(!flag){
//cout<<"Jinaliale";
for(int t=j+1;t<l;t++){
// cout<<points[i].x-points[t].x<<endl;
// int kn=((float)points[i].y-(float)points[t].y)/(points[i].x-points[t].x);
float k1=((float)points[t].y-(float)points[i].y)*(points[j].x-points[i].x);
float k2=((float)points[j].y-(float)points[i].y)*(points[t].x-points[i].x);
if(k1==k2){
//cout<<kn<<endl;
temp+=1;}
}
//cout<<max<<endl;
temp+=repeatcount;
cout<<repeatcount;
}
max=max>temp?max:temp;
// cout<<"max "<<max<<endl;
}
flag=false;
repeatcount=0;
}
return max;
}
};
感觉思维还是存在问题的,对于特殊情况的考虑不是特别充分。此外,当前代码循环层数太多,仍需要改进。
推荐阅读