AlgoViz Lab交互式算法学习Algorithms first
直线上最多的点数 · 交互式算法学习
找到同一直线上的最多点数。
#149 · 数学
直线上最多的点数
Max Points on a Line
points = [[1,1],[2,2],[3,3]]线性序列3 个关键状态
步骤 1固定 (1,1) 为锚点。
anchor(1,1)
0(2,2)
1(3,3)
2推荐
固定锚点统计约分斜率
时间
O(n²)空间 O(n)对每个锚点把 dy/dx 用 gcd 约分为唯一哈希键。
1function maxPoints(p) {2 let best = 1;3 const gcd = (a, b) => b ? gcd(b, a % b) : Math.abs(a);4 for (let i = 0; i < p.length; i++) {5 const map = new Map();6 for (let j = i + 1; j < p.length; j++) {7 let dx = p[j][0] - p[i][0],8 dy = p[j][1] - p[i][1],9 g = gcd(dx, dy);10 dx /= g;11 dy /= g;12 if (dx === 0) dy = 1;13 else if (dy === 0) dx = 1;14 else if (dx < 0) {15 dx = -dx;16 dy = -dy17 }18 const k = dy + ',' + dx;19 map.set(k, (map.get(k) || 1) + 1);20 best = Math.max(best, map.get(k))21 }22 }23 return best;24}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int maxPoints(int[][] points) {3 int n = points.length;4 int ans = 1;5 for (int i = 0; i < n; ++i) {6 int x1 = points[i][0], y1 = points[i][1];7 for (int j = i + 1; j < n; ++j) {8 int x2 = points[j][0], y2 = points[j][1];9 int cnt = 2;10 for (int k = j + 1; k < n; ++k) {11 int x3 = points[k][0], y3 = points[k][1];12 int a = (y2 - y1) * (x3 - x1);13 int b = (y3 - y1) * (x2 - x1);14 if (a == b) {15 ++cnt;16 }17 }18 ans = Math.max(ans, cnt);19 }20 }21 return ans;22 }23}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
直线上最多的点数 · 解法对比
找到同一直线上的最多点数。
- 测试用例
points = [[1,1],[2,2],[3,3]]- 题目分类
- 数学
- 解法对比
- 2
枚举两点定义直线再计数
每对点定义一条线，再扫描所有点是否满足叉积为零。
- 时间
O(n³)- 空间
O(1)
固定锚点统计约分斜率
对每个锚点把 dy/dx 用 gcd 约分为唯一哈希键。
- 时间
O(n²)- 空间
O(n)