107.直线上最多的点数
题目
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
思路
核心思路：固定一个点，统计其他点相对于它的斜率
1. 为什么固定一个点？
如果一条直线经过多个点，那么这条直线上的所有点相对于这条直线上的任意一个点，斜率都相同（或垂直）。所以我们可以枚举每一个点作为基准点，然后计算其他所有点相对于这个基准点的斜率，斜率相同的点就在同一条直线上。
2. 如何处理重复点？
如果有重复的点，它们相对于基准点的斜率相同，但它们本身就是同一个位置。我们需要单独统计与基准点重合的点的个数，因为这些点必然和基准点在一条直线上（任何经过基准点的直线都经过它们）。在处理斜率时，把这些重合点排除在外，最后加到结果里。
3. 如何表示斜率以避免浮点误差？
斜率 dy/dx 如果用浮点数表示，可能会因精度问题导致误判（比如 1/3 和 2/6 理论上相同，但浮点数可能不同）。更好的方法是使用最简分数来表示斜率，即用 (dx, dy) 的最简整数比（分子分母互质，且统一符号约定，比如规定分母为正，或分子分母同号）。这样可以用字符串或 Pair 作为哈希表的键。 - 对于水平线（dy=0）：斜率表示为 (0, 1) 或其他约定。 - 对于垂直线（dx=0）：斜率表示为 (1, 0)。
4. 具体步骤
- 初始化最大点数 maxCount = 0。
- 遍历每个点 i 作为基准点：
- 初始化哈希表 slopeMap，记录每个斜率出现的次数（不包括基准点自身和重合点）。
- 初始化 samePointCount = 1（基准点自身算一个）。
- 遍历每个点 j（j != i）：
- 如果 points[j] 与基准点坐标相同，则 samePointCount++。
- 否则计算相对坐标 dx = points[j].x - points[i].x，dy = points[j].y - points[i].y。
- 化简 (dx, dy) 为最简形式：求出 gcd(|dx|, |dy|)，然后 dx /= g, dy /= g。为了统一符号，可以规定 dx 为正（如果 dx==0 则 dy 为正），或者规定 (dx, dy) 的第一项非负。
- 将化简后的 (dx, dy) 作为键存入哈希表，计数加 1。
- 遍历完所有 j 后，哈希表中的最大值加上 samePointCount 就是以基准点为起点的某条直线上的最大点数。
- 更新全局 maxCount。
- 返回 maxCount。
class Solution {
fun maxPoints(points: Array<IntArray>): Int {
if (points.size <= 2) return points.size
var ans = 0
for (i in points.indices) {
// 以 points[i] 作为起点时，
// 记录每种斜率出现了多少次
val map = HashMap<String, Int>()
// 重复点数量
var same = 0
// 经过当前起点的最多点数（不含重复点时）
var maxCount = 0
for (j in i + 1 until points.size) {
var dx = points[j][0] - points[i][0]
var dy = points[j][1] - points[i][1]
// 如果两个点完全一样，单独计数
if (dx == 0 && dy == 0) {
same++
continue
}
// 处理竖直线
if (dx == 0) {
dy = 1
}
// 处理水平线
else if (dy == 0) {
dx = 1
} else {
// 约分，保证同一条线的斜率写法一致
val g = gcd(kotlin.math.abs(dx), kotlin.math.abs(dy))
dx /= g
dy /= g
// 统一符号，保证 (1, -1) 和 (-1, 1) 视为同一个方向
if (dx < 0) {
dx = -dx
dy = -dy
}
}
val key = "$dy/$dx"
val count = map.getOrDefault(key, 0) + 1
map[key] = count
maxCount = maxOf(maxCount, count)
}
// 当前起点本身要算 1 个
// same 是重复点，也都在这条线上
ans = maxOf(ans, maxCount + same + 1)
}
return ans
}
private fun gcd(a: Int, b: Int): Int {
var x = a
var y = b
while (y != 0) {
val t = x % y
x = y
y = t
}
return x
}
}
复杂度
- 时间复杂度: O(n²)，每个基准点需要遍历其他所有点。
- 空间复杂度: O(n)，哈希表最多存储 n-1 个斜率。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!