共计 1869 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 149. 直线上最多的点数 ，难度为 艰难。
Tag :「数学」、「枚举」、「哈希表」
给你一个数组 points，其中 $points[i] = [x_i, y_i]$ 示意 X-Y 立体上的一个点。求最多有多少个点在同一条直线上。
示例 1：
输出：points = [[1,1],[2,2],[3,3]]
输入：3示例 2：
输出：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输入：4提醒：
- $1 <= points.length <= 300$
- $points[i].length == 2$
- $-10^4 <= x_i, y_i <= 10^4$
points中的所有点 互不雷同
模仿（枚举直线 + 枚举统计）
咱们晓得，两个点能够确定一条线。
因而一个奢侈的做法是先枚举两条点（确定一条线），而后查看其余点是否落在该线中。
为了防止除法精度问题，当咱们枚举两个点 $i$ 和 $j$ 时，不间接计算其对应直线的 斜率 和 截距，而是通过判断 $i$ 和 $j$ 与第三个点 $k$ 造成的两条直线斜率是否相等（斜率相等的两条直线要么平行，要么重合，平行须要 $4$ 个点来惟一确定，咱们只有 $3$ 个点，所以能够间接断定两直线重合）。
代码：
class Solution {public int maxPoints(int[][] ps) {
int n = ps.length;
int ans = 1;
for (int i = 0; i < n; i++) {int[] x = ps[i];
for (int j = i + 1; j < n; j++) {int[] y = ps[j];
int cnt = 2;
for (int k = j + 1; k < n; k++) {int[] p = ps[k];
int s1 = (y[1] - x[1]) * (p[0] - y[0]);
int s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) cnt++;
}
ans = Math.max(ans, cnt);
}
}
return ans;
}
}- 工夫复杂度：$O(n^3)$
- 空间复杂度：$O(1)$
优化（枚举直线 + 哈希表统计）
依据「奢侈解法」的思路，枚举所有直线的过程不可避免，但统计点数的过程能够优化。
具体的，咱们能够先枚举所有可能呈现的 直线斜率 （依据两点确定一条直线，即枚举所有的「点对」），应用「哈希表」统计所有 斜率 对应的点的数量，在所有值中取个 $max$ 即是答案。
一些细节：在应用「哈希表」进行保留时，为了防止精度问题，咱们间接应用字符串进行保留，同时须要将 斜率 约洁净。
代码：
class Solution {public int maxPoints(int[][] ps) {
int n = ps.length;
int ans = 1;
for (int i = 0; i < n; i++) {Map<String, Integer> map = new HashMap<>();
// 由以后点 i 收回的直线所通过的最多点数量
int max = 0;
for (int j = i + 1; j < n; j++) {int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);
String key = (a / k) + "_" + (b / k);
map.put(key, map.getOrDefault(key, 0) + 1);
max = Math.max(max, map.get(key));
}
ans = Math.max(ans, max + 1);
}
return ans;
}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}
}- 工夫复杂度：枚举所有直线的复杂度为 $O(n^2)$；令坐标值的最大差值为 $m$，
gcd复杂度为 $O(\log{m})$。整体复杂度为 $O(n^2 \times \log{m})$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.149 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
