难度: Medium
给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。
设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。
示例：
输入： [[0,0],[1,1],[1,0],[2,0]] 输出： [0,2] 解释： 所求直线穿过的3个点的编号为[0,2,3]
提示：
2 <= len(Points) <= 300len(Points[i]) = 2运行时间: 87 ms
内存: 16.2 MB
class Solution:
def bestLine(self, points: List[List[int]]) -> List[int]:
ans = []
mx = 0
for i, (x, y) in enumerate(points):
d = defaultdict(list)
for j in range(i + 1, len(points)):
xx, yy = points[j]
if x == xx:
d[inf].append(j)
else:
d[(yy - y) / (xx - x)].append(j)
l = max(d.values(), key=len, default=[])
if len(l) > mx:
mx = len(l)
ans = [i, l[0]]
return ans
该题解采用了通过每一对点计算斜率的方法来确定穿过最多点的直线。首先，对于每个点 i，使用一个哈希表 d 来记录以该点为起点，其他点与之构成的直线的斜率和对应的点的索引列表。遍历每个点 j (j > i)，根据两点确定的斜率将 j 索引加入到哈希表的对应斜率键下。特别地，当两点 x 坐标相同时，斜率为无穷大，使用 inf 表示。之后，检查对于当前点 i，哪个斜率对应的列表最长，即这些点都在同一条直线上。如果这个数量超过了之前记录的最大数量 mx，则更新最大数量和记录直线经过的点的最小两个索引。最终返回穿过最多点的直线的最小两个点的索引。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def bestLine(self, points: List[List[int]]) -> List[int]:
ans = [] # 用于存储结果的两个点的索引
mx = 0 # 记录当前发现的最大共线点数
for i, (x, y) in enumerate(points):
d = defaultdict(list) # 字典，键为斜率，值为通过点i和具有该斜率的其他点的索引列表
for j in range(i + 1, len(points)):
xx, yy = points[j]
if x == xx: # x坐标相同，斜率为无穷大
d[inf].append(j)
else: # 计算斜率并存储
d[(yy - y) / (xx - x)].append(j)
l = max(d.values(), key=len, default=[]) # 找到包含点最多的斜率对应的列表
if len(l) > mx: # 如果这个列表的长度大于当前记录的最大长度
mx = len(l) # 更新最大长度
ans = [i, l[0]] # 更新结果
return ans
为了避免浮点数计算中的精度问题，可以通过使用整数进行斜率的比较来解决。具体操作是不直接计算斜率的浮点值，而是计算斜率的分子与分母（即纵坐标差与横坐标差），并将它们的最大公约数约简后同时保存。这样可以用两个整数（分子和分母的比值）唯一确定一个斜率，避免了浮点数的精度问题。
在实际编程中，我们通常使用一个特殊的标记（如Python中的`float('inf')`或其他唯一标识）来表示斜率为无穷大。这个方法实际上是把垂直线的斜率标记为一个特殊值，从而区别于其他斜率。由于这个值是预定义且唯一的，因此不会与其他基于算术运算得到的斜率值产生哈希冲突。
基于斜率的方法是判断点是否共线的直接和有效方式。斜率的计算只涉及基本的算术运算，易于实现，且计算效率高。相比之下，基于角度的方法需要使用三角函数，这在计算上更复杂且效率较低。而基于距离的方法则需要考虑更多的几何属性和计算，同样增加了实现的复杂性。因此，基于斜率的方法因其简洁性和效率在许多算法中被优先使用。