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

LeetCode: Max Points on a Line

2024-07-14 07:54:51   229人阅读

LeetCode: 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.

地址：https://oj.leetcode.com/problems/max-points-on-a-line/

    当初刷这一道题的时候总是超时，后来参考了一个博客（时间太久了，忘了那个博客的链接了）才做出来的。具体的思想是这样的：我们记经过点数最多的直线上编号最大的那个点为 i，则这个i的取值范围在2～n之间，因为一条直线至少经过两个点。这样，我们就可以遍历i的范围，即每个子问题为在编号1～i之间找出一条直线，这条直线必须通过点i并且直线通过的点最多。函数sub_maxPoints就是解决上述的子问题，变量same_points用来记录和点i坐标相同的点的个数（包括点i本身），变量vertical_points用来记录垂直于X轴的点个数，hash_table用来记录斜率为k的直线的点个数，最后max_value用来记录hash_table中以及vertical_points中最大的那个值。在函数内部我们先把编号为i的点的坐标记录下来，然后遍历1到i-1之间的点，有三种情况的点出现，1）与点i重合的点，此时更新变量same_points；2)与点i形成垂直线的点，此时更新vertical_points；3）与点i形成斜率为k的点，此时更新hash_table[k]中的值。最后返回same_points和max_value的和。注意，在实际代码循环中i可以从编号3开始。具体代码如下：

 

 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     map<double,int> hash_table;13     int maxPoints(vector<Point> &points) {14         int n = points.size();15         if (n < 3)16             return n;17         int max_res = 2;18         int t;19         for (int i = 3; i <= n; ++i){20             t = sub_maxPoints(points,i);21             if (t > max_res)    max_res = t;22         }23         return max_res;24     }25     int sub_maxPoints(vector<Point> &points, int n){26         if (n < 3)27             return n;28         hash_table.clear();29         int x = points[n-1].x;30         int y = points[n-1].y;31         int same_points = 1;32         int vertical_points = 0;33         int max_value = http://www.mamicode.com/0;34         double k;35         for (int i = 0; i < n-1; ++i){36             if (x == points[i].x && y == points[i].y)37                 ++same_points;38             else if(x == points[i].x){39                 ++vertical_points;40                 if (vertical_points > max_value)41                     max_value =http://www.mamicode.com/ vertical_points;42             } else{43                 k = 1.0 * (y - points[i].y) / (x - points[i].x);44                 if (++hash_table[k] > max_value)45                     max_value =http://www.mamicode.com/ hash_table[k];46             }47         }48         return max_value + same_points;49     }50 };

 


联系
我们