算法-数学-斜率-直线上最多的点数

算法-数学-斜率-直线上最多的点数

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++) {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];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/