欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每天一道LeetCode-----平面上n个点,计算最多有多少个点在一条直线上

程序员文章站 2022-04-01 19:58:55
...

Max Points on a Line

原题链接Max Points on a Line

每天一道LeetCode-----平面上n个点,计算最多有多少个点在一条直线上

给出2D平面中的n个坐标点,计算最多有多少个点在一条直线上

一条直线可以用斜率表示,即如果已知(x1,y1)(x2,y2),那么斜率为(y2y1)/(x2x1) ,所以固定一个点,然后遍历其他点,将不同的斜率到个数的映射记录在map中,然后求最大的

思路是这样,但是由于浮点数计算有误差,导致斜率的计算不是准确的,所以不能直接记录斜率。因为斜率是由Δy/Δx计算得到的,那么可以采用<Δx,Δy>到个数的映射,不过需要将ΔxΔy化为最简的形式,这样,就可以将<Δx,Δy>这个数值对相等看成是斜率相等

化为最简的方法是找到两个数的最大公约数,使用辗转相除法,计算步骤是

  • 用第一个数除以第二个数得到余数
  • 如果余数为0,则第二个数就是最大公约数,返回
  • 否则,用第二个数除以余数,回到步骤1(即将第二个数作为新的第一个数,将余数作为新的第二个数)

另外需要注意的一点是坐标点可能存在重合的情况

代码如下

/**
 * 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) {
        int count = 0;
        for(int i = 0; i < points.size(); ++i)
        {
            /* 固定points[i],遍历其他点,记录不同斜率个数,找最大的 */
            std::map<std::pair<int, int>, int> m;
            int cnt = 0;
            int samePointCnt = 0;
            for(int j = i + 1; j < points.size(); ++j)
            {
                /* 记录重合点 */
                if(points[i].x == points[j].x && points[i].y == points[j].y)
                    ++samePointCnt;
                else
                {
                    int xDiff = points[i].x - points[j].x;
                    int yDiff = points[i].y - points[j].y;
                    /* 计算最大公约数 */
                    int g = gcd(xDiff, yDiff);
                    xDiff /= g;
                    yDiff /= g;
                    /* 添加到map中 */
                    cnt = std::max(cnt, ++m[std::make_pair(xDiff, yDiff)]);
                }
            }
            count = std::max(count, cnt + samePointCnt + 1);
        }
        return count;
    }
private:
    int gcd(int a, int b)
    {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
};

这里之所以用map而不用unordered_map是因为std::pair没有hash函数,所以如果要使用后者,就需要自己实现hash函数

相关标签: leetcode