欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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```*