当前位置: 首页 > news >正文

直线上最多的点数

优质博文: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 时,我们令 my=1;当 my 为 0 时,我们令 mx=1 即可。

经过上述操作之后,即可得到最终的二元组 (mx,my)。在本题中,因为点的横纵坐标取值范围均为 [−104,104],所以斜率 slope=
mx/my中,mx 落在区间 [−2×104,2×104] 内,my 落在区间 [0,2×104] 内。注意到 32 位整数的范围远超这两个区间,因此我们可以用单个 32 位整型变量来表示这两个整数。具体地,我们令 val=my+(2×104+1)×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;}Map<Integer, Integer> map = new HashMap<Integer, 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.Entry<Integer, 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 为点的数量。主要为哈希表的开销。

http://www.lryc.cn/news/431576.html

相关文章:

  • 经济管理专业数据库介绍
  • 【C++ Primer Plus习题】11.1
  • [数据库][oracle]ORACLE EXP/IMP的使用详解
  • 中国各银行流动性比例数据(2000-2022年)
  • MACOS安装配置前端开发环境
  • Docker 配置国内镜像源
  • AI模块在人工智能中扮演着什么样的角色
  • VM Workstation虚拟机AlmaLinux 9.4操作系统安装(桌面版安装详细教程)(宝塔面板的安装),填补CentOS终止支持维护的空白
  • 【学习笔记】卫星通信NTN 3GPP标准化进展分析(三)- 3GPP Release17 内容
  • 【SQL】常见语句合集
  • Cozer必备!一站式解锁扣子全网最全插件集锦(三)
  • 1-2宿主环境
  • Java进阶13讲__第九讲
  • 上海市计算机学会竞赛平台2024年8月月赛丙组等差数列的素性
  • VR虚拟展厅的应用场景有哪些?
  • Go 语言版本管理——Goenv
  • C#中的各种画刷, PathGradientBrush、线性渐变(LinearGradientBrush)和径向渐变的区别
  • 如何在Mac中修改pip的镜像源
  • MySQL你必须知道的事
  • Ceph RBD使用
  • Spark MLlib模型训练—回归算法 Random forest regression
  • 华为OD机试真题-数大雁-2024年OD统一考试(E卷)
  • Oracle数据迁移:导出与导入的详细指南
  • SpringBoot实现前后端传输加密设计
  • X 射线测厚仪-高效精准,厚度测量的卓越之选
  • 10款好用的文件加密软件排行榜|文件加密管理软件推荐(合集篇)
  • 服务器蓝屏该怎么办
  • Elasticsearch:使用 inference API 进行语义搜索
  • PVE开启核显直通
  • 使用 Bert 做文本分类,利用 Trainer 框架实现 二分类,事半功倍