3.max-points-on-a-line 直线上的最多点-蒲公英云

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

题目描述

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;
    }
};