3.max-points-on-a-line 直线上的最多点

我不是女神ヾ 2022-06-06 07:20 188阅读 0赞

## 题目描述 ##

Given *n* points on a 2D plane, find the maximum number of points that lie on the same straight line.

给定一个二维平面上的n个点，找到一条直线上面的点最多，求得这个直线上的点的数目

## 题目解析 ##

这个题目如果用暴力遍历的想法去做，本身并不难思考，难点在于将各种情况都考虑好。

先说一下我的遍历的方法是：

双层循环，外循环是循环每一个点，内循环是从外循环遍历的点后面一个点开始 循环到最后一个点。

每次循环，计算斜率，保存在map容器中，斜率相同时，map.second++。

这样循环的原因是：

因为两点确定一条直线，外循环保证的是，必须通过这个外循环遍历的这个点，其他点上的斜率，如果斜率相同自然是在同一条直线上的。

内循环 从外循环遍历的后一个点开始的原因是，如果需要经过前面的点的线，在前面外循环遍历时，已经记录了正确答案，比如给定 (0,0) (1,1) (2,2)外循环计算了(0,0) 有两个点相同斜率了之后，再遍历(1,1)时，就不需要再去把(0,0)再计算一遍，尽管在计算(1,1)时并不是正确的。

不过这样遍历明显不是最好的方法。

需要考虑的特殊情况：

1、平面中给出的只有一个点

2、为竖直的线，无法计算斜率，单独拿出来计算

3、重合的点

代码如下：

/**
     * 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:
        int maxPoints(vector<Point> &points) 
        {
            if (points.size() < 3) return points.size();
            
            int start = 0;
            int max = 0;
            
            for (start = 0; start < points.size(); start++)
            {
                map<float, int> tmpMap;
                int perp = 0;
                int dup = 0;
                int tmpmax = 0;
                
                for (int i = start + 1; i < points.size(); i++)
                {
                    int tmpx = points[i].x - points[start].x;
                    int tmpy = points[i].y - points[start].y;
                    
                    if (0 == tmpx && 0 == tmpy)
                    {
                        dup++;
                    }
                    else if (0 == tmpx)
                    {
                        perp++;
                    }
                    else
                    {
                        float tmpSlope = (float)tmpy / tmpx;
                        
                        map<float, int>::iterator ite = tmpMap.find(tmpSlope);
                        if (ite == tmpMap.end())
                        {
                            tmpMap.insert(make_pair(tmpSlope, 1));
                            tmpmax = (0 == tmpmax) ? 1 : tmpmax;
                        }
                        else
                        {
                            ite->second++;
                            tmpmax = (tmpMap[tmpSlope] > tmpmax) ? tmpMap[tmpSlope] : tmpmax;
                        }
                        
                    }
                    
                }
                
                tmpmax = (perp > tmpmax) ? perp : tmpmax;
                tmpmax += dup;
                
                max = (tmpmax > max) ? tmpmax : max;
                
                //if (max > points.size() - start) break;
            }
            
            return max + 1;
        }
    };