LeetCode 149直线上最多的点数 | 哈希表处理斜率引言直线上最多的点数Max Points on a Line是 LeetCode 第 149 题难度为 Hard。题目要求在给定的点集合中找到位于同一条直线上的最多点数。这道题是平面几何与哈希表结合的经典案例考察了如何将几何问题转化为算法问题并通过哈希表高效地处理斜率计算和去重。这道题的核心挑战在于如何处理斜率计算中的精度问题和垂直线的特殊情况。通过将斜率规范化为字符串表示或使用最大公约数约简我们可以将同一类斜率的直线归为一组然后使用哈希表高效地找出包含最多点的直线。问题分析题目描述给定一个数组 points其中每个元素是一个点的坐标 [x, y]返回在同一条直线上最多的点数。例如输入 [[1,1],[2,2],[3,3]]返回 3因为这三个点都在同一条直线上。输入 [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]返回 4因为 [1,1],[4,1],[2,3],[1,4] 在同一条斜率为 -1 的直线上。问题特点这道题有几个关键挑战。首先是斜率计算的精度问题。斜率通常用 dy/dx 表示但浮点数精度有限可能导致两个本应相同的斜率被误判为不同。因此我们需要使用整数或字符串来表示斜率避免浮点数精度问题。其次是垂直线的处理。当两点 x 坐标相同时斜率为无穷大或 undefined不能简单地用浮点数表示。常见的处理方式是用字符串 inf 或特殊值来表示垂直线。第三是重复点的处理。如果数组中包含重复的点它们与任何其他点形成的直线都包含这些重复点需要特殊处理。解决方案暴力枚举加哈希表from collections import defaultdict from math import gcd def maxPoints(points): if len(points) 2: return len(points) max_count 0 for i in range(len(points)): slopes defaultdict(int) same_point 1 for j in range(i 1, len(points)): dx points[j][0] - points[i][0] dy points[j][1] - points[i][1] if dx 0 and dy 0: same_point 1 else: g gcd(dx, dy) dx // g dy // g if dx 0: dx -dx dy -dy slope_key (dx, dy) slopes[slope_key] 1 for slope in slopes: max_count max(max_count, slopes[slope] same_point) max_count max(max_count, same_point) return max_count这段代码展示了暴力枚举加哈希表的解法。以每个点作为基准点计算与其他所有点的斜率将相同斜率的点归为一组。使用最大公约数 gcd 来约简斜率避免浮点数精度问题。斜率规范化斜率规范化的关键在于将 dy/dx 转换为唯一的整数表示。本文中我们使用 (dx, dy) 作为斜率的键其中 dx 和 dy 是约简后的整数。约简使用最大公约数dx dx / gcd(dx, dy)dy dy / gcd(dx, dy)。为了保证唯一性我们还需要将 dx 和 dy 调整为统一的符号如果 dx 0或者 dx 0 且 dy 0则取相反数。这种规范化确保了同一斜率的所有点都会映射到同一个键。处理特殊情况垂直线dx 0和水平线dy 0是两个重要的特殊情况。对于垂直线所有点的 x 坐标相同斜率键为 (1, 0) 或类似表示。对于水平线所有点的 y 坐标相同斜率键为 (0, 1) 或类似表示。重复点的处理是在遍历过程中维护一个 same_point 计数器每次遇到与基准点重合的点时加一。这些重复点与任何其他点形成的直线都包含它们。算法详解为什么枚举基准点算法枚举每个点作为基准点计算其他所有点与基准点的斜率。这种方法基于一个重要观察如果有多个点位于同一条直线上那么以这条直线上的任意一点作为基准点其他所有点与基准点形成的斜率都应该相同。因此对于每条包含点 i 的直线以 i 为基准点时这直线上的所有点包括 i都会有相同的斜率。我们只需要统计以 i 为基准点时同一斜率上有多少个点。时间复杂度分析对于 n 个点算法需要 O(n²) 的时间复杂度因为我们需要枚举每个点作为基准点然后遍历其他所有点。哈希表操作是 O(1)所以总时间复杂度是 O(n²)。空间复杂度是 O(n)用于存储哈希表。在最坏情况下所有斜率都不同哈希表可能包含 n-1 个条目。优化减少重复计算上述算法存在一些重复计算如果点 i 和点 j 在同一条直线上我们会在分别以 i 和 j 为基准点时各计算一次这条直线。但这种优化很难实现而且可能会增加代码复杂度因此 O(n²) 的解法在面试中是可接受的。代码实现Python 实现from collections import defaultdict from math import gcd def maxPoints(points): if len(points) 2: return len(points) max_count 0 for i in range(len(points)): slopes defaultdict(int) same_point 1 for j in range(i 1, len(points)): dx points[j][0] - points[i][0] dy points[j][1] - points[i][1] if dx 0 and dy 0: same_point 1 else: g gcd(dx, dy) dx // g dy // g if dx 0: dx -dx dy -dy elif dx 0 and dy 0: dy -dy slopes[(dx, dy)] 1 if slopes: max_count max(max_count, max(slopes.values()) same_point) else: max_count max(max_count, same_point) return max_countJava 实现public int maxPoints(int[][] points) { if (points.length 2) { return points.length; } int max 0; for (int i 0; i points.length; i) { MapString, Integer slopeCount new HashMap(); int same 1; for (int j i 1; j points.length; j) { int dx points[j][0] - points[i][0]; int dy points[j][1] - points[i][1]; if (dx 0 dy 0) { same; } else { int g gcd(dx, dy); dx / g; dy / g; if (dx 0) { dx -dx; dy -dy; } else if (dx 0 dy 0) { dy -dy; } String key dx , dy; slopeCount.put(key, slopeCount.getOrDefault(key, 0) 1); } } if (slopeCount.isEmpty()) { max Math.max(max, same); } else { for (int count : slopeCount.values()) { max Math.max(max, count same); } } } return max; } private int gcd(int a, int b) { a Math.abs(a); b Math.abs(b); while (b ! 0) { int temp b; b a % b; a temp; } return a; }复杂度分析时间复杂度时间复杂度为 O(n²)其中 n 是点的数量。对于每对点我们计算一次斜率并进行哈希表操作。虽然有优化空间如剪枝但在面试中 O(n²) 是可以接受的。空间复杂度空间复杂度为 O(n)用于存储哈希表。在最坏情况下哈希表可能包含 n-1 个条目。边界情况处理少于三个点当点的数量小于等于 2 时所有点都在同一条直线上因为两点确定一条直线直接返回点的数量。垂直线当多个点 x 坐标相同时如 [[1,1],[1,2],[1,3]]dx 0gcd(0, dy) dy约简后斜率为 (0, 1) 或 (0, -1)。通过符号标准化所有垂直线的斜率都会映射到同一个键。水平线当多个点 y 坐标相同时如 [[1,1],[2,1],[3,1]]dy 0gcd(dx, 0) |dx|约简后斜率为 (1, 0) 或 (-1, 0)。通过符号标准化所有水平线的斜率都会映射到同一个键。重复点当存在重复点时这些点与任何其他点形成的直线都包含它们。因此我们需要维护一个 same_point 计数器在统计每个斜率上的点数时加上 same_point。整数溢出在 Java 等语言中dx 和 dy 的计算可能导致整数溢出。由于坐标范围通常在 [-10⁴, 10⁴] 左右差值在 [-2×10⁴, 2×10⁴] 左右gcd 和约简不会导致溢出。但使用 long 类型可以提供更大的安全范围。测试用例def test_max_points(): assert maxPoints([[1,1],[2,2],[3,3]]) 3 assert maxPoints([[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]) 4 assert maxPoints([[0,0]]) 1 assert maxPoints([[0,0],[0,0]]) 2 assert maxPoints([[0,0],[1,1],[2,2]]) 3 assert maxPoints([[1,1],[1,1],[2,2],[2,2]]) 4 assert maxPoints([[0,0],[1,1],[-1,-1]]) 3 print(所有测试用例通过)实际应用场景直线上最多点数问题在现实中有很多应用。在计算机视觉中用于检测共线的特征点。在地理信息系统GIS中用于识别在同一直线上的地标。在数据分析中用于检测线性相关的变量。从更广泛的角度看这个问题展示了如何将几何问题转化为离散数学问题并通过哈希表进行高效求解。这种转化思想在算法设计中非常重要。总结直线上最多的点数问题展示了哈希表在处理几何问题中的灵活应用。通过将斜率规范化为整数元组我们可以将同一斜率的点归为一组然后使用哈希表高效地统计每条直线上的点数。这个问题的关键在于正确处理斜率计算的精度问题和特殊情况垂直线、水平线、重复点。使用最大公约数约简和符号标准化是解决这些问题的标准技巧。希望通过本文的讲解读者能够掌握这种将几何问题离散化并使用哈希表求解的思路。