LeetCode 149. 直线上最多的点数
目录
题目描述
题意分析
给一堆平面整点，问「存在一条直线，最多能同时穿过其中几个点」，返回这个最大数量。注意直线是任意的，不限于水平或竖直，也不需要输出直线本身。
约束里点数很小（数百量级），坐标是绝对值上万的整数。点数小意味着允许平方级枚举；坐标是整数则是一个强信号——两点之间的横纵差值都是整数，这条直线的方向完全可以用一对整数来精确描述，不必引入实数。
这里有个必须点明的坑：直觉上会想用
dy / dx这个浮点斜率当哈希键，但浮点数除法带来舍入误差，两条本该相同的斜率算出来可能差在最后几位有效数字上，被当成两条不同的直线；反过来两条略有差异的斜率也可能舍入成同一个值。正确做法是用最简分数表示方向：把(dy, dx)同时除以它们的最大公约数，再统一符号，得到唯一的整数对作为键。整个过程只用整数运算，没有任何精度损失。边界包括：竖直线（
dx为 0，不能做除法）、水平线（dy为 0）、负方向（(1, 2)和(-1, -2)是同一条直线的方向，必须归一化成同一个键）、题目允许存在重复点（同一坐标出现多次，它们与任何直线的关系都一样，要单独计数）、以及总点数不超过 2 时答案就是点数本身，因为任意两点必定共线。
解法：枚举基准点 + 方向向量规范化
核心思路
一条直线由两个点确定。枚举每个点
i作为基准点，统计其他点j相对它的方向；方向相同的点与基准点共线，最大分组大小加上基准点本身，就是经过i的最多点数。不能直接用浮点斜率
dy / dx：除零需要特判，且不同分数可能因精度舍入碰撞。应把方向表示为整数对(dx, dy)，再除以gcd(abs(dx), abs(dy))约分。约分后还要统一符号，否则
(1,1)与(-1,-1)会被分到不同组。本文规定dx为正；当dx == 0时规定dy为正。这样水平线统一成(1,0)，竖直线统一成(0,1)，每个几何方向只有一种编码。对固定基准点，哈希表计数的是“其他点”的数量，所以更新全局答案时要加 1。题目保证点互不相同；若取消该条件，还需单独统计与基准点重合的点。
解题步骤
- 枚举基准点
i，为它创建方向计数表。- 枚举
j > i，计算dx = xj - xi、dy = yj - yi。- 用最大公约数约分
dx、dy。- 若
dx < 0，或dx == 0 && dy < 0，同时翻转二者符号。- 将规范化后的整数对作为哈希键并累加计数，用“计数 + 1”更新答案。
例如相对基准点的方向
(2,2)、(-3,-3)都会规范化为(1,1)；方向(0,-4)会规范化为(0,1)。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int maxPoints(int[][] points) {
int answer = 1;
for (int i = 0; i < points.length; i++) {
Map<String, Integer> count = new HashMap<>();
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];
int divisor = gcd(Math.abs(dx), Math.abs(dy));
dx /= divisor;
dy /= divisor;
if (dx < 0 || (dx == 0 && dy < 0)) {
dx = -dx;
dy = -dy;
}
String direction = dx + "," + dy;
int sameDirection = count.getOrDefault(direction, 0) + 1;
count.put(direction, sameDirection);
answer = Math.max(answer, sameDirection + 1);
}
}
return answer;
}
private int gcd(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
}
func maxPoints(points [][]int) int {
answer := 1
for i := 0; i < len(points); i++ {
count := make(map[[2]int]int)
for j := i + 1; j < len(points); j++ {
dx := points[j][0] - points[i][0]
dy := points[j][1] - points[i][1]
divisor := gcd(abs(dx), abs(dy))
dx /= divisor
dy /= divisor
if dx < 0 || dx == 0 && dy < 0 {
dx = -dx
dy = -dy
}
direction := [2]int{dx, dy}
count[direction]++
if count[direction]+1 > answer {
answer = count[direction] + 1
}
}
}
return answer
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func abs(value int) int {
if value < 0 {
return -value
}
return value
}
复杂度分析
- 时间复杂度：$O(n^2 \log C)$，其中 $C$ 是坐标差的最大值；每对点计算一次最大公约数。坐标范围固定时通常记为 $O(n^2)$。
- 空间复杂度：$O(n)$，固定一个基准点时，哈希表最多保存 $n-1$ 个方向。
关键点总结
- 枚举基准点后，二维共线问题转化为方向分组计数。
- 用约分后的整数对表示方向，避免浮点精度和竖直线除零问题。
- 最大公约数只消除倍数，符号规范化负责合并相反向量。
- 哈希表不含基准点自身，因此局部计数要加 1。
易错点总结
- 使用
double斜率可能把不同方向误判为相同，也必须额外处理dx == 0。- 只做最大公约数约分、不统一符号，会把
(1,1)和(-1,-1)分开。- 只统一
dx < 0而漏掉竖直方向，会把(0,1)、(0,-1)分开。- 局部方向计数没有包含基准点，直接拿它更新答案会少算 1。
- 若输入允许重复点，
dx == 0 && dy == 0会使最大公约数为 0，必须另计重合点；本题的点互不相同，因此无需该分支。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1232. 缀点成线 | 简单 | 单条直线的共线判定 |
| 面试题 16.14. 最佳直线 | 中等 | 同时要求返回直线上的点 |
| 447. 回旋镖的数量 | 中等 | 按距离分组的点对统计 |
| 593. 有效的正方形 | 中等 | 整数运算避免开方误差 |
| 1071. 字符串的最大公因子 | 简单 | 辗转相除法的另一类应用 |