Leetcode149_Max_Points_on_a_Line
程序员文章站
2022-04-15 12:42:15
...
- 题目
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Input: [[1,1],[2,2],[3,3]]
Output: 3
- 翻译
就是给一组点,找到其中数量最多的都在一条直线上的点
- 解答
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points)
{
if ( points.size() < 2 )
return points.size();
int ret = 0;
//遍历所有点
for ( int i = 0; i < points.size(); i++ )
{
map<pair<int,int>,int> lines;
int localmax = 0, overlap = 0, vertical = 0;
//这里只检查i之后的点,之前的组合情况已经算过了,这不是排列问题
for ( int j = i + 1; j < points.size(); j++ )
{
//点i和点j重合的情况
if ( points[j].x == points[i].x && points[j].y == points[i].y )
{
overlap++;
}
//点j和点i的x相等
else if ( points[j].x == points[i].x )
{
vertical++;
}
else //保证a,b不会同为0,至少a不为0,这样gcd不会为0
{
// 相当于计算斜率,但是double用来算斜率是不精确的
int a = points[j].x - points[i].x, b = points[j].y - points[i].y;
int gcd = GCD(a,b);
// 使用最大公约数,则相同直线上的点都可以对应到同一pair中
//同时都经过点i,所以都是一条直线上的点
a /= gcd;
b /= gcd;
//同一条线对应的点加一
lines[make_pair(a,b)]++;
//更新当前在一条直线的点的最多的数量
localmax = max(lines[make_pair(a,b)],localmax);
}
// 比较垂直x轴斜率不存在的线上点的数量是不是比其他直线都多
localmax = max(vertical,localmax);
//这些更新都是对j遍历的结果来说的
}
//更新ret值,这个更新是对i遍历的结果来说的
ret = max( ret , localmax + overlap + 1 );
}
return ret;
}
private:
int GCD(int a,int b)
{
if ( b == 0 )
return a;
else
return GCD(b,a % b);
}
};