题解 | #直线上的牛# 哈希表 gcd

知识点

哈希表 最大公因数gcd

思路

我们如果按照一般的直线方程y=kx+b的形式会产生k和b是浮点数的情况，这样会产生精度问题。我们换这样一个思路，遍历整个数组，枚举一个点作为直线的起点；现在已经选定好一个点做起点后，我们再遍历整个数组（这次取起点以外的n-1个点），分别计算他们之间的横纵坐标的差值对，用哈希表统计差值对，一样的差值对说明在一条直线上。哈希表中的最大值则是选定当前起点的最大值。

统计差值对，如果两个数都是正数，那么可以除以gcd让他们互质得到最简形式，如果存在一个是0，那么让另外一个是1即可，因为不存在相同的两个点，我们不会有差值都是0的情况。

哈希表的话，由于cpp语言特性上没有支持pair做key的哈希表实现，我们可以用map代替。其他语言（比如py）可以。

时间复杂度上，我们有一个二重枚举，再加上map插入的时间复杂度，总体时间复杂度为

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param points int整型vector<vector<>> 
     * @return int整型
     */
    using PII = pair<int, int>;
    int maxPoints(vector<vector<int> >& points) {
        int res = 0;
        for (int i = 0; i < points.size(); i ++) {
            res = max(res, check(points, i) + 1);
        }
        return res;
    }
    int check(vector<vector<int> >& ps, int u) {
        map<PII, int> mp;
        int x = ps[u][0], y = ps[u][1];
        int res = 0;
        for (int i = 0; i < ps.size(); i ++) {
            if (i == u) continue;
            int dx = x - ps[i][0], dy = y - ps[i][1];
            if (dx < 0) dx = -dx, dy = -dy;
            if (dx == 0) dy = 1;
            else if (dy == 0) dx = 1;
            else {
                auto t = __gcd(abs(dx), abs(dy));
                dx /= t;
                dy /= t;
            }
            res = max(++ mp[make_pair(dx, dy)], res);
        }
        return res;
    }
};