首页 > 代码库 > 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 };