给定2D平面上的n个点,找到位于同一直线上的最大点数
程序员文章站
2022-04-01 18:41:46
...
本题源自LeetCode
--------------------------------------------------------
二重遍历,第一次遍历确定一个点a,在遍历剩下的点b.分三种情况 1 a,b 重合 2 a,b 垂直 3 ,a,b是一条b/a 的直线。
int maxPoints(vector<Point> &points) {
int length=points.size();
if(length==0)
return 0;
if(length==1)
return 1;
int ret=0;
for(int i=0;i<length;i++){
int currentMax=1;
int dup=0; //记录重复点
int vcnt=0; //记录垂直点
map<double,int> linemap; //键为斜率
for(int j=i+1;j<length;j++){
//必须定义为double 因为要计算斜率
double x=points[i].x-points[j].x;
double y=points[i].y-points[j].y;
if(x==0&&y==0){ //重复
dup++;
}else if(x==0){ //垂直
if(vcnt==0)
vcnt=2;
else
vcnt++;
currentMax=max(currentMax,vcnt);
}else{ //斜率
double k=y/x;
if(linemap[k]==0)
linemap[k]=2;
else
linemap[k]++;
currentMax=max(currentMax,linemap[k]);
}
}
ret=max(currentMax+dup,ret);
}
return ret;
}
推荐阅读
-
leetcode 给定二维平面上的n个点,找到位于同一直线上的最大点数
-
编程题—给定位于二维平面上的n个点,求出位于同一条直线上的最大点数
-
给定二维平面上的n个点,找到位于同一直线上的最大点数
-
LeetCode:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定2D平面上的n个点,找到位于同一直线上的最大点数
-
[leetcode]给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
Leetcode打卡2:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上java实现
-
枚举:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上