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 中的所有点 互不相同。

解题思路

问题的解决关键在于如何有效地计算和比较斜率，可以通过规范化斜率和使用哈希表来记录点的分布，来找出最多共线的点。

1. 斜率计算：

   • 对每个点 points[i]，计算与其他点的斜率并存入哈希表 obj。
   • 斜率的计算可以通过 (y2 - y1) / (x2 - x1) 得到，但为了避免浮点数计算带来的精度问题，通常使用整数表示斜率，即使用 (dy, dx) 形式，其中 dy = y2 - y1，dx = x2 - x1。
   • 对于垂直线的情况要特殊处理。

2. 标准化斜率：

   • 斜率应当被标准化为最简分数形式，以确保相同斜率的点可以被正确识别。
   • 使用最大公约数 (GCD) 来简化斜率。

3. 使用哈希表统计：

   • 使用一个哈希表来记录每个点的斜率对应的点的数量。
   • 遍历每个点，将其他点的斜率存入哈希表，并更新最多的点数。

4. 处理重复点：

   • 对于重复的点，应当单独处理，确保它们被正确计入共线点的总数。

5. 更新全局最大值：

   • 在每个点的计算中，算出最多共线的点数 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+