跳至主要內容

149. 直线上最多的点数


149. 直线上最多的点数open in new window

🔴   🔖  几何 数组 哈希表 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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 - y1dx = 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直线镜像 🔒open in new window数组 哈希表 数学
2152穿过所有点的所需最少直线数量 🔒open in new window位运算 几何 数组 5+
2280表示一个折线图的最少线段数open in new window几何 数组 数学 2+