[LeetCode]Max Points on a Line

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.

对点遍历，找到对每个点共线的最大点数，所有点的最大值即是全局最大值。

Note：对每个值用Hash table记录当前点和其他点的斜率，key为斜率值，竖直的线的斜率位double(INT_MAX)，value是出现的个数；

可能出现相同坐标的点。

 1 /**
 2  * Definition for a point.
 3  * struct Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() : x(0), y(0) {}
 7  *     Point(int a, int b) : x(a), y(b) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxPoints(vector<Point>& points) {
13         if(points.size()<3) return points.size();
14         int result=0;
15         unordered_map<double,int> showed;
16         for(int i=0;i<points.size()-1;i++)
17         {
18             showed.clear();
19             int samePoint=1;
20             for(int j=i+1;j<points.size();j++)
21             {
22                 if(points[i].x==points[j].x)
23                 {
24                     if(points[i].y==points[j].y)
25                     {
26                         samePoint++;
27                     }
28                     else
29                     {
30                         if(showed.find(double(INT_MAX))!=showed.end())
31                         {
32                             showed[double(INT_MAX)]+=1;
33                         }
34                         else
35                         {
36                             showed[double(INT_MAX)]=1;
37                         }
38                     }
39                 }
40                 else
41                 {
42                     double slope=(points[j].y-points[i].y)*1.0/(points[j].x-points[i].x);
43                     if(showed.find(slope)!=showed.end())
44                     {
45                         showed[slope]+=1;
46                     }
47                     else
48                     {
49                         showed[slope]=1;
50                     }
51                 }
52             }
53             int max_i=0;
54             for(unordered_map<double,int>::iterator iter=showed.begin();iter!=showed.end();iter++)
55             {
56                 if(max_i<iter->second)
57                 {
58                     max_i=iter->second;
59                 }
60             }
61             max_i=max_i+samePoint;
62             if(result<max_i)
63             {
64                 result=max_i;
65             }
66         }
67         
68         return result;
69     }
70 };

[LeetCode]Max Points on a Line

Max Points on a Line

相关推荐