题目分析

这个题目比较经典，和Leetcode149题几乎相同，有很多人吐槽这个问题，说题目不清晰，样例看不懂，这里我说明一下，Leetcode149题是找出直线上最多的点数，一条直线最多能穿过多少个点，题意非常清晰。而这个题目的意思是找到这个直线，因为两个点才能确定一条直线，因此返回直线上索引最小的两个点。如这条直线穿过了3，6，7，9这四个点，那么就返回3和6即可。

数学+哈希表

这个题目有暴力解法，确定前两个点，判断第三个点是否在前两个点所在直线上。判断的方法有很多，可以根据前两个点确定直线方程，然后代入第三个点进行计算。也可以利用数学中向量共线知识进行求解。
$$\frac{y3 - y2}{x3 - x2} = \frac{y2 - y1}{x2 - x1}$$
其中推荐使用向量共线进行求解，因为确定直线方程时可能存在着精度问题。但是这个两个方法的时间复杂度都是$O(n^3)$，我们就不过多介绍。

这里介绍一种哈希表存储的方法。我们只要枚举第i个点，然后比较从i + 1到最后的点与第一个点的斜率。假设枚举第1个点，然后比较第2个点，第3个点…与第一个点的斜率，如果斜率相同，说明它们都在一条直线上。那么我们将斜率作为键进行保存，是不是就可以统计出来了呢？

这里要注意的是精度问题，因为除法可能会损失精度。我们应该如何去做呢？

斜率的计算公式是
$$ k = \frac{y2 - y1}{x2 - x1}$$
如果我们用一个pair记录分子和分母，那么就用pair来查询，而且不损失精度。这时我们要保证分子和分母是互质的，而且分子和分母都取反后和原pair是相同的。如{2, 6}和{1, 3}是相同的，{2, 6}和{-2, -6}是相同的。我们可以去分母和分子的最大公约数，然后让它们都除以这个数，可以保证互质。然后让分子都变为大于等于0的数，如果分子等于0，那么让分子变为正数。那么{-2, -6}就会变成{1, 3}。{0, -10}就会变成{0, 1}。

**还要注意的是C++中unordered_map容器无法直接存储pair，vector等元素作为key，要实现哈希函数和判断相等的函数。因为pair中存在判断相等的函数，因此我们只需要实现哈希函数。写一个类，重载调用操作符operator()**。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

这个题目应该这样求解，使用C++语言难度还是比较大的，考察的知识点也很多，希望小伙伴们能够自己实现一遍。

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class PairHash {
public:
    size_t operator() (const pair<int, int> p) const {
        return hash<int>()(p.first) ^ hash<int>()(p.second);
    }
};

class Solution {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
        vector<int> res = { 0, 1 };
        int maxi = 2;
        for (int i = 0; i < points.size() - maxi; i++) {
            unordered_map<pair<int, int>, vector<int>, PairHash> dic;
            for (int j = i + 1; j < points.size(); j++) {
                int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];
                int g = gcd(dx, dy);
                dx = dx / g;
                dy = dy / g;
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                if (dx == 0 && dy < 0) {
                    dy = -dy;
                }
                pair<int, int> p = { dx, dy };
                if (dic.count(p)) { dic[p][0]++; }
                else { dic[p] = { 2, i, j }; }
                if (dic[p][0] > maxi || (dic[p][0] == maxi && dic[p][1] < res[0]) || (dic[p][0] == maxi && dic[p][1] == res[0] && dic[p][2] < res[1])) {
                    maxi = dic[p][0];
                    res[0] = dic[p][1];
                    res[1] = dic[p][2];
                }
            }
        }
        return res;
    }

    int gcd(int a, int b) {
        int c;
        while (b) {
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
};

刷题总结

纯数学或者是几何的题目往往难度都比较复杂，需要考虑到精度问题，小伙伴们要使用一些奇技淫巧去躲避它。