[LeetCode]Max Points on a Line

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

[LeetCode Source]

思路：对每一个节点求和其他节点的斜率，用hash_map统计斜率相同的点数。时间O(N^2)，空间O(N)。应该有更简单可以在O(1)空间的算法，暂时没想出来。

这道题目AC率低的原因是由于各种边界条件，要注意：

1）有重复点的情况；

2）点数少于2的情况；

3）有垂直点（斜率为无穷）的情况。

遍历节点时注意已经遍历的节点不用再遍历了，避免重复遍历。

比如已经对前i个节点求了最大值，对第i+1个节点就不用再遍历前i个节点算斜率，，因为之前节点已经对i+1点求过斜率算过最大值。

代码如下：

/** * 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) {int size = points.size();if(size<=1)return size;int res = 0;for(int i=0;i<size;++i){int local = 1;int Vertical = 0;int Dup = 0;double k= 0.0;unordered_map<double,int> map;for(int j=i+1;j<size;++j){ //只需对i+1大的值的点求线，因为以之前为小于i+1起点的直线已经遍历过i+1点，再求解就是重复遍历了if(points[i].x == points[j].x){if(points[i].y == points[j].y)Dup++; //统计重复的点数elseVertical++; //统计水平的点数}else{k = (points[j].y-points[i].y)*1.0/(points[j].x-points[i].x);map[k]==0?map[k]=2:map[k]++; //计算在同一直线上的点local = max(local,map[k]); //和该节点在同一直线上的最大点数}}local = max(local+Dup,Vertical+Dup+1);//该节点加上重复的节点，注意水平和重复节点有可能是最大值res = max(local,res);//计算所有解中的最大的节点}return res;}};

自己战胜自己是最可贵的胜利。