LeetCode:149_Max Points on a line | 寻找一条直线上最多点的数量 | Hard

题目: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.

这道题需要稍微转变一下思路,用斜率来实现,试想找在同一条直线上的点,怎么判断在一条直线上,唯一的方式也只有斜率可以完成,我开始没想到,后来看网友的思路才想到的,下面是简单的实现:
其中有一点小技巧,利用map<double, int>来存储具有相同斜率值的的点的数量,简洁高效。

 1 /* 
 2     Definition for a point
 3 */
 4 // struct Point {
 5 //     int x;
 6 //     int y;
 7 //     Point():x(0),y(0) {}
 8 //     Point (int a, int b):x(0), y(0) {}
 9 // };
10 
11 int maxPoints(vector<Point> &points) {
12     if (points.empty())
13         return 0;
14     if (points.size() <= 2) 
15         return points.size();
16 
17     int numPoints = points.size();
18     map<double, int> pmap;    //存储斜率-点数对应值
19     int numMaxPoints = 0;
20 
21     for (int i = 0; i != numPoints - 1; ++i) {
22         int numSamePoints = 0, numVerPoints = 0;  //针对每个点分别做处理
23         
24         pmap.clear();
25         
26         for (int j = i + 1; j != numPoints; ++j) {
27             if(points[i].x != points[j].x) {
28                 double slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
29                 if (pmap.find(slope) != pmap.end())
30                     ++ pmap[slope];   //具有相同斜率值的点数累加
31                 else 
32                     pmap[slope] = 1;
33             }
34             else if (points[i].y == points[j].y) 
35                 numSamePoints ++;   //重合的点
36             else
37                 numVerPoints ++;    //垂直的点
38 
39         }
40         map<double, int>::iterator it = pmap.begin();
41         for (; it != pmap.end(); ++ it) {
42             if (it->second > numVerPoints)
43                 numVerPoints = it->second;
44         }
45         if (numVerPoints + numSamePoints > numMaxPoints) 
46             numMaxPoints = numVerPoints + numSamePoints;
47     }
48     return numMaxPoints + 1;
49 }

 

上一篇:ramnit病毒


下一篇:ASP.NET MVC 中使用用户控件