首页 > 代码库 > [LeetCode]Max Points on a Line

[LeetCode]Max Points on a Line

2024-07-04 07:03:10   228人阅读

题目：

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

算法分析：

定义最大直线为符合相同条件的直线中通过点最多的那条直线。

对每个点p，计算其它的点与p形成的直线的斜率，斜率相同的点个数加1，即是通过点p的最大直线。

时间复杂度O(N^2)，空间复杂度O(N)。

几个需要注意的事项：

1 斜率的计算

  对点a和b，斜率r = (a.y - b.y)/(a.x - b.x)。

  对于code来讲，x与y都是int，但是斜率不总是整数。

   一种方法是用float表示斜率。这种方法存在一个精度问题。

   第二种方法，可以用(a.y - b.y, a.x - b.x)来表示斜率。但是这个方法编码比较麻烦，一方面要对这2个数进行约分，不然不好比较；另外一方面是要以pair做map的key。

   为了偷懒采用了第一种方法，所幸LeetCode的用例里面没有覆盖到精度问题（写code算了一下，float最小可以分辨出1/11864338 和1/11864337）。

   除了精度问题外，还有2个边界条件需要考虑：

  1.1 a.x == b.x && a.y != b.y

      代表点a与b形成的直线为平行于y轴的直线，斜率为正无穷。

  1.2 a.x == b.x && a.y == b.y

      代表a与b重合。

2 关于内层循环里j的起始点

   j从外层循环i+1开始是没有问题的。假设全局最大直线上的所有点的最小下标为I。对于小于I的点i，因为i不在全局最大直线上，所以将它剔除出后面点的计算不影响max的结果。对于I，max已经是我们想要的结果了，后面的计算都已经没有意义。

 

AC代码：

 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         map<float, int> status;
14         map<float, int>::iterator iter;
15         float r = 0;
16         int status2 = 0;
17         int samePoints = 0;
18         int max = 0;
19         int maxTmp = 0;
20         
21         if(points.size() < 2){
22             return points.size();
23         }
24         
25         for(int i = 0; i < points.size()-1; i++){
26             if(max >= points.size() - i){
27                 return max;
28             }
29             status.clear();
30             status2 = 1;
31             samePoints = 0;
32             maxTmp = 0;
33             for(int j = i+1; j < points.size(); j++){
34                 if(points[i].x == points[j].x){
35                     if(points[i].y == points[j].y){
36                         samePoints++;
37                     }else{
38                         status2++;
39                     }
40                 }else{
41                     r = (float)(points[j].y - points[i].y) / (float)(points[j].x - points[i].x);
42                     if(status.find(r) != status.end()){
43                         status[r]++;
44                     }else{
45                         status[r] = 2;
46                     }
47                 }
48             }
49             
50             for(iter = status.begin(); iter != status.end(); iter++){
51                 if(iter->second > maxTmp){
52                     maxTmp = iter->second;
53                 }
54             }
55             
56             if(status2 > maxTmp){
57                 maxTmp = status2;
58             }
59             
60             maxTmp += samePoints;
61             
62             if(maxTmp > max){
63                 max = maxTmp;
64             }
65         }
66         return max;
67     }
68 };

 


联系
我们