做网站需要什么电脑配置,建设银行兰州分行网站,活动发布类网站开发,dw网站怎么做搜索优质博文#xff1a;IT-BLOG-CN
题目
给你一个数组points#xff0c;其中points[i] [xi, yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。
示例 1#xff1a; 输入#xff1a;points [[1,1],[2,2],[3,3]] 输出#xff1a;3
示例 2#xff1a; 输入IT-BLOG-CN
题目
给你一个数组points其中points[i] [xi, yi]表示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 -104 xi, yi 104 points中的所有点 互不相同 代码
方法一哈希表
思路及解法
我们可以考虑枚举所有的点假设直线经过该点时该直线所能经过的最多的点数。
假设我们当前枚举到点 i如果直线同时经过另外两个不同的点 j 和 k那么可以发现点 i 和点 j 所连直线的斜率恰等于点 i 和点 k 所连直线的斜率。
于是我们可以统计其他所有点与点 i 所连直线的斜率出现次数最多的斜率即为经过点数最多的直线的斜率其经过的点数为该斜率出现的次数加一点 i 自身也要被统计。
如何记录斜率
需要注意的是浮点数类型可能因为精度不够而无法足够精确地表示每一个斜率因此我们需要换一种方法来记录斜率。
一般情况下斜率可以表示为的形式因此我们可以用分子和分母组成的二元组来代表斜率。但注意到存在形如1/2 2/4 这样两个二元组不同但实际上两分数的值相同的情况所以我们需要将分数 化简为最简分数的形式。
将分子和分母同时除以二者绝对值的最大公约数可得二元组。令 则上述化简后的二元组为 (mx,my)。此外因为分子分母可能存在负数为了防止出现形如 −1/ 2 1/−2 的情况我们还需要规定分子为非负整数如果 my 为负数我们将二元组中两个数同时取相反数即可。
特别地考虑到 mx 和 my 两数其中有一个为 0 的情况因为题目中不存在重复的点因此不存在两数均为 0 的情况此时两数不存在数学意义上的最大公约数因此我们直接特判这两种情况。当 mx 为 0 时我们令 my1当 my 为 0 时我们令 mx1 即可。
经过上述操作之后即可得到最终的二元组 (mx,my)。在本题中因为点的横纵坐标取值范围均为 [−104,104]所以斜率 slope mx/my中mx 落在区间 [−2×104,2×104] 内my 落在区间 [0,2×104] 内。注意到 32 位整数的范围远超这两个区间因此我们可以用单个 32 位整型变量来表示这两个整数。具体地我们令 valmy(2×1041)×mx 即可。
优化
最后我们再加四个小优化
在点的总数量小于等于 2 的情况下我们总可以用一条直线将所有点串联此时我们直接返回点的总数量即可 当我们枚举到点 i 时我们只需要考虑编号大于 i 的点到点 i 的斜率因为如果直线同时经过编号小于点 i 的点 j那么当我们枚举到 j 时就已经考虑过该直线了 当我们找到一条直线经过了图中超过半数的点时我们即可以确定该直线即为经过最多点的直线 当我们枚举到点 i假设编号从 0 开始时我们至多只能找到 n−i 个点共线。假设此前找到的共线的点的数量的最大值为 k如果有 k≥n−i那么此时我们即可停止枚举因为不可能再找到更大的答案了。
class Solution {public int maxPoints(int[][] points) {int n points.length;if (n 2) {return n;}int ret 0;for (int i 0; i n; i) {if (ret n - i || ret n / 2) {break;}MapInteger, Integer map new HashMapInteger, Integer();for (int j i 1; j n; j) {int x points[i][0] - points[j][0];int y points[i][1] - points[j][1];if (x 0) {y 1;} else if (y 0) {x 1;} else {if (y 0) {x -x;y -y;}int gcdXY gcd(Math.abs(x), Math.abs(y));x / gcdXY;y / gcdXY;}int key y x * 20001;map.put(key, map.getOrDefault(key, 0) 1);}int maxn 0;for (Map.EntryInteger, Integer entry: map.entrySet()) {int num entry.getValue();maxn Math.max(maxn, num 1);}ret Math.max(ret, maxn);}return ret;}public int gcd(int a, int b) {return b ! 0 ? gcd(b, a % b) : a;}
}时间复杂度 O(n2 × log m)其中 n 为点的数量m 为横纵坐标差的最大值。最坏情况下我们需要枚举所有 n 个点枚举单个点过程中需要进行 O(n) 次最大公约数计算单次最大公约数计算的时间复杂度是 O(logm)因此总时间复杂度为 O(n2 × logm)。
空间复杂度 O(n)其中 n 为点的数量。主要为哈希表的开销。
