leetcode 给定二维平面上的n个点,找到位于同一直线上的最大点数
程序员文章站
2022-04-02 18:49:37
...
我们都知道,两点可以确定一条直线,而且可以写成y = ax + b的形式,在一条直线上的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率,每个斜率代表一条直线,对每一条直线,带入所有的点看是否共线,并计算个数,这是整体的思路。
1-当两个点重合时,无法确定一条直线,但这也是共线的情况,需要特殊处理。
2-当斜率不存在时,由于两个点(x1, y1)和(x2, y2)的斜率k表示为(y2 - y1) / (x2 - x1),那么当x1 = x2时斜率不存在,这种共线情况需要特殊处理。
3-我们需要用到哈希表来记录斜率和共线点个数之间的映射,其中第一种重合点的情况我们假定其斜率为INT_MIN,第二种情况我们假定其斜率为INT_MAX,这样都可以用map映射了。
4-我们还需要定一个变量duplicate来记录重合点的个数,最后只需和哈希表中的数字相加即为共线点的总数。
#include <iostream>
#include <string>
#include <map>
#include <vector>
/**
*@date: 2020-3-27
*@brief: 给定二维平面上的n个点,找到位于同一条直线上的最大点数
*@attention:使用map数据结构
*/
using namespace std;
struct Point{
int x,y;
Point(){x=0;y=0;}//初始化
Point(int a,int b):x(a),y(b){}
};
class Solution
{
public:
int max(int a,int b){
return a>b?a:b;
}
int maxPoint(vector<Point> &points){
int size=points.size();
if(size<=2){
return size; //如果只是一个点或者两个点直接返回
}
int res=0;
for(int i=0;i<size;i++)//遍历所以的点
{
map<float,int> kmap;//存放斜率为k的点数
int d=1; //主要是用来记录重合点的个数
for(int j=i+1;j<size;j++){
if(points[i].x==points[j].x){
if(points[i].y==points[j].y){
d++; //1.两点重合
}else{
kmap[INT_MAX]++; //2.斜率不存在的
}
}else{
//3.用来记录斜率存在的情况
float K=(points[j].y-points[i].y)/(points[j].x-points[i].x);
kmap[K]++;
}
}
//进行比较三种情况的最大数
res=max(res,d);
for(auto it=kmap.begin();it!=kmap.end();it++){
res=max(res,it->second+d);//it->first为key it->second 为value
}
}
return res;
}
};
int main(int argc, char *argv[])
{
vector<Point> points;
int n;
cin>>n;
int x,y;
for(int i=0;i<n;i++){
cin>>x>>y;
Point point(x,y);
points.push_back(point);
}
Solution solu;
int maxnum=solu.maxPoint(points);
cout<<maxnum<<endl;
return 0;
}
*测试用例:
[(0,0),(1,1),(0,0)]
对应输出应该为:
3```*
上一篇: 使用O2OA二次开发搭建企业办公平台(十七)信息开发篇:信息发布的审批功能
下一篇: 流程设计
推荐阅读
-
leetcode 给定二维平面上的n个点,找到位于同一直线上的最大点数
-
编程题—给定位于二维平面上的n个点,求出位于同一条直线上的最大点数
-
给定二维平面上的n个点,找到位于同一直线上的最大点数
-
LeetCode:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定2D平面上的n个点,找到位于同一直线上的最大点数
-
[leetcode]给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
Leetcode打卡2:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上java实现
-
枚举:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上