题目分析
这个题目比较经典,和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++语言难度还是比较大的,考察的知识点也很多,希望小伙伴们能够自己实现一遍。
1 | #include<iostream> |
刷题总结
纯数学或者是几何的题目往往难度都比较复杂,需要考虑到精度问题,小伙伴们要使用一些奇技淫巧去躲避它。