首页 > 代码库 > LeetCode: Max Points on a Line
LeetCode: Max Points on a Line
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 };