149. 直线上最多的点数
149. 直线上最多的点数
🔴 🔖 几何
数组
哈希表
数学
🔗 力扣
LeetCode
题目
Given an array of points
where points[i] = [xi, yi]
represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Constraints:
1 <= points.length <= 300
points[i].length == 2
-10^4 <= xi, yi <= 10^4
- All the
points
are unique.
题目大意
给你一个数组 points
,其中 points[i] = [xi, yi]
表示 X-Y
平面上的一个点。求最多有多少个点在同一条直线上。
points
中的所有点 互不相同。
解题思路
问题的解决关键在于如何有效地计算和比较斜率,可以通过规范化斜率和使用哈希表来记录点的分布,来找出最多共线的点。
斜率计算:
- 对每个点
points[i]
,计算与其他点的斜率并存入哈希表obj
。 - 斜率的计算可以通过
(y2 - y1) / (x2 - x1)
得到,但为了避免浮点数计算带来的精度问题,通常使用整数表示斜率,即使用(dy, dx)
形式,其中dy = y2 - y1
,dx = x2 - x1
。 - 对于垂直线的情况要特殊处理。
- 对每个点
标准化斜率:
- 斜率应当被标准化为最简分数形式,以确保相同斜率的点可以被正确识别。
- 使用最大公约数 (GCD) 来简化斜率。
使用哈希表统计:
- 使用一个哈希表来记录每个点的斜率对应的点的数量。
- 遍历每个点,将其他点的斜率存入哈希表,并更新最多的点数。
处理重复点:
- 对于重复的点,应当单独处理,确保它们被正确计入共线点的总数。
更新全局最大值:
- 在每个点的计算中,算出最多共线的点数
max
,包括当前、重复点以及斜率相同的点,更新全局最大值res
。
- 在每个点的计算中,算出最多共线的点数
复杂度分析
- 时间复杂度:
O(n^2)
,每个点都与其他点进行比较。 - 空间复杂度:
O(n)
,用于存储斜率的哈希表。
代码
/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function (points) {
const gcd = (a, b) => {
if (b === 0) return a;
return gcd(b, a % b);
};
let n = points.length,
res = 0;
if (n <= 2) return n;
for (let i = 0; i < n; i++) {
let obj = {},
overlap = 0,
max = 0,
vertical = 0;
for (let j = i + 1; j < n; j++) {
let dx = points[i][0] - points[j][0],
dy = points[i][1] - points[j][1];
// 重复点
if (dx == 0 && dy == 0) {
overlap++;
continue;
}
// 垂直线
if (dx == 0) {
vertical++;
continue;
}
// 规范化斜率
const g = gcd(dy, dx);
const slope = `${dy / g}/${dx / g}`;
obj[slope] = (obj[slope] || 0) + 1;
max = Math.max(max, obj[slope]);
}
// 加上垂直线的情况
max = Math.max(max, vertical);
// 加上当前点和重复点
res = Math.max(res, max + overlap + 1);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
356 | 直线镜像 🔒 | 数组 哈希表 数学 | ||
2152 | 穿过所有点的所需最少直线数量 🔒 | 位运算 几何 数组 5+ | ||
2280 | 表示一个折线图的最少线段数 | 几何 数组 数学 2+ |