LeetCode149 - 直线上最多的点数
题目
给定一组 X-Y 平面上的点,返回位于同一条直线上的最大点数。
例子:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
约束:
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
- 没有重复的点
分析
这是一个 hard 级别的题目,但私以为主要是细节要考虑全面,整体思想倒不是很难。
题目已经限制了最多有 300 个点,那么 n<sup>2</sup> 的时间复杂度是可以接受的。以此为出发点,众所周知两点可以确定一条直线,那么只要计算出任意两点的直线,就可以判断其他的点在不在这条线上了。这里选择使用「点斜式」来表示直线,以便通过哈希表迅速完成「点是否在线上」的判断。
那么出现了两个细节问题:
- 斜率有可能不存在。
- 斜率会有误差。
问题 1 比较简单,单独判断一下就好。问题 2 则采用一个通用的办法来规避:String 代替 Double。具体来讲,要找出两个数的最大公约数,分别除以它化成最简分式的形式。例如 20/6=3.3333333
现在直接把字符串 10/3
当作 key 就好了。
java 代码
class Solution {
public int maxPoints(int[][] points) {
if (points.length <= 2)
return points.length;
int result = 0;
for (int i = 0; i < points.length; i++) {
Map<String, Integer> map = new HashMap<>(); // 斜率 -> 点个数
for (int j = 0; j < points.length; j++) {
if (i == j) continue;
String slope = calcSlope(points[i], points[j]);
map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 2);
}
for (int c : map.values())
if (c > result) result = c;
}
return result;
}
private String calcSlope(int[] p1, int[] p2) {
if (p1[0] == p2[0]) // 斜率不存在
return "N";
int dx = p1[1] - p2[1];
int dy = p1[0] - p2[0];
int g = gcd(dx, dy);
if (g != 0) {
dx /= g;
dy /= g;
}
return dx + "/" + dy;
}
private int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
}
License:
禁止转载到非自托管的内容平台,禁止用于 AI 训练