灯饰 技术支持 东莞网站建设,网站怎么做百科,网络公司商标注册,十大高端网站设计算法-数学-斜率-直线上最多的点数
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/max-points-on-a-line/
1.2 题目描述
给你一个数组 points #xff0c;其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
2 暴力搜索斜率…算法-数学-斜率-直线上最多的点数
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/max-points-on-a-line/
1.2 题目描述
给你一个数组 points 其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
2 暴力搜索斜率相同点
2.1 思路
遍历所有节点比较斜率如果斜率相同就统计最后返回最大统计数。
2.2 代码
class Solution {public int maxPoints(int[][] points) {int result 1;for (int i 0; i points.length; i) {int[] first points[i];for (int j i 1; j points.length; j) {int[] second points[j];// 只要到这里说明至少有两个点// 两个点就能构成一条直线所以至少是2// 这里相当于是i和j确定了一条直线继续统计经过这条直线上的点数int cnt 2;for (int k j 1; k points.length; k) {int[] third points[k];// 计算斜率 (y1 - y0) / (x1 - x0) 是否相等// 因为涉及除不尽的情况所以交还两边的除数来相乘int k1 (second[0] - first[0]) * (third[1] - second[1]);int k2 (third[0] - second[0]) * (second[1] - first[1]);if (k1 k2) {cnt;}}result Math.max(result, cnt);}}return result;}
}2.3 时间复杂度 O(N^3)
2.4 空间复杂度
O(1)
3 Hash表法
3.1 思路
3.2 代码
class Solution {public int maxPoints(int[][] ps) {int n ps.length;int result 1;for (int i 0; i n; i) {MapString, 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];int 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, 1) 1);// 更新经过当前点的直线的最大点数// 即比较所有经过当前点的直线上的点数取最大者max Math.max(max, map.get(key));}// 更新结果result Math.max(result, max);}return result;}// 求公约数int gcd(int a, int b) {return b 0 ? a : gcd(b, a % b);}
}3.3 时间复杂度 3.4 空间复杂度
O(N)
参考
https://leetcode.cn/problems/max-points-on-a-line/solutions/842114/zhi-xian-shang-zui-duo-de-dian-shu-by-le-tq8f/https://leetcode.cn/problems/max-points-on-a-line/solutions/842391/gong-shui-san-xie-liang-chong-mei-ju-zhi-u44s/
