直线上最多的点数
优质博文: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 为点的数量。主要为哈希表的开销。
相关文章:

直线上最多的点数
优质博文:IT-BLOG-CN 题目 给你一个数组points,其中points[i] [xi, yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例 1: 输入:points [[1,1],[2,2],[3,3]] 输出:3 示例 2: 输入&am…...

经济管理专业数据库介绍
本文介绍了四个经济管理专业数据库:国研网全文数据库、EPS数据平台、中经网、Emerald全文期刊库(管理学)。 一、国研网全文数据库 国研网是国务院发展研究中心主管、北京国研网信息有限公司承办的大型经济类专业网站。国研网教育版”是国研…...

【C++ Primer Plus习题】11.1
问题: 解答: main.cpp #include <iostream> #include <fstream> #include "Vector.h" #include <time.h> using namespace std; using namespace VECTOR;int main() {ofstream fout;fout.open("randwalk.txt");srand(time(0));double d…...
[数据库][oracle]ORACLE EXP/IMP的使用详解
导入/导出是ORACLE幸存的最古老的两个命令行工具,其实我从来不认为Exp/Imp是一种好的备份方式,正确的说法是Exp/Imp只能是一个好的转储工具,特别是在小型数据库的转储,表空间的迁移,表的抽取,检测逻辑和物理…...

中国各银行流动性比例数据(2000-2022年)
介绍中国银行业2000年至2022年间的流动性比例数据,涵盖500多家银行,包括城市商业银行、城镇银行、大型商业银行、股份制银行、民营银行、农村合作银行、农村商业银行、农村信用社等。这些数据对于理解中国银行业的流动性状况至关重要,有助于投…...

MACOS安装配置前端开发环境
官网下载安装Mac版本的谷歌浏览器以及VS code代码编辑器,还有在App Store中直接安装Xcode(里面自带git); node.js版本管理器nvm的下载安装如下: 参考B站:https://www.bilibili.com/video/BV1M54y1N7fx/?sp…...

Docker 配置国内镜像源
由于 GFW 的原因,在下载镜像的时候,经常会出现下载失败的情况,此时就可以使用国内的镜像源。 什么是镜像源:简单来说就是某个组织(学校、公司、甚至是个人)先通过某种手段将国外的镜像下载下来,…...
AI模块在人工智能中扮演着什么样的角色
AI模块在人工智能(AI)中扮演着核心和关键的角色。它们是构成AI系统的基础单元,负责实现AI系统的各种智能功能。以下是AI模块在人工智能中扮演的具体角色: 功能实现的核心:AI模块集成了实现特定智能功能所需的算法、数据…...

VM Workstation虚拟机AlmaLinux 9.4操作系统安装(桌面版安装详细教程)(宝塔面板的安装),填补CentOS终止支持维护的空白
目录 AlmaLinux介绍 AlmaLinux操作系统的安装 1、下载镜像文件 2、新建虚拟机 (1)点击创建新的虚拟机 (2)打开虚拟机向导后,选择“自定义”安装,然后点击“下一步” (3)选择虚…...

【学习笔记】卫星通信NTN 3GPP标准化进展分析(三)- 3GPP Release17 内容
一、引言: 本文来自3GPP Joern Krause, 3GPP MCC (May 14,2024) Non-Terrestrial Networks (NTN) (3gpp.org) 本文总结了NTN标准化进程以及后续的研究计划,是学习NTN协议的入门。 【学习笔记】卫星通信NTN 3GPP标准化进展分析(一ÿ…...

【SQL】常见语句合集
SQL常见语句合集 一. 新建表1.1 语句1.2 结果 二. 新增数据2.1 语句2.2 结果 三. 新增字段列3.1 语句3.2 结果3.3 扩展 四. 更新指定数据4.1 语句4.2 结果 五. 更新指定列5.1 语句(长度) 六. 删除字段列6.1 语句 七. 删除指定数据7.1 语句 八. 查询 一. …...
Cozer必备!一站式解锁扣子全网最全插件集锦(三)
俗话说,工欲善其事必先利其器! 用过Coze的朋友都知道,插件在Coze里的重要性。插件库就相当于武器库,一个好的插件,就相当于一件趁手的兵器,可以让你事半功倍! 程哥精心整理了Coze最常用和好用…...

1-2宿主环境
什么是宿主环境 指的是程序运行所必须的依赖环境。Android系统和ios系统是两个不同的宿主环境,安卓版的app是不能在ios系统上运行的。 小程序的宿主环境 🍕🍕🍕 -手机微信是小程序的宿主环境 通信的主体 🍔&…...

Java进阶13讲__第九讲
Stream流 1. 案例初体验 package cn.hdc.oop9.stream.using;import java.util.LinkedList; import java.util.List; import java.util.stream.Collectors; import java.util.stream.Stream;public class t1 {public static void main(String[] args) {LinkedList<String&g…...
上海市计算机学会竞赛平台2024年8月月赛丙组等差数列的素性
题目描述 给定三个整数 nn,aa 与 dd,表示一个项数为 nn 的等差数列,首项为 aa,公差为 dd。 请统计,从这个等差数列中有多少数字是素数 输入格式 三个整数: nn,aa 与 dd 输出格式 单个整数…...

VR虚拟展厅的应用场景有哪些?
虚拟展厅作为一种利用虚拟现实技术构建的三维展示空间,其应用场景广泛且多样。视创云展为企业虚拟展厅搭建提供技术支持。以下是一些主要的应用场景: 1. 博物馆和艺术展览 文物保护与展示: 在博物馆中,为了保护珍贵的文物和艺术…...
Go 语言版本管理——Goenv
Go 语言版本管理——Goenv 命令安装 goenv安装和切换 Go 版本 goenv 是一个专门管理 Go 语言版本的工具。 命令 安装 goenv github-goenv git clone https://github.com/go-nv/goenv.git ~/.goenv echo export GOENV_ROOT"$HOME/.goenv" >> ~/.bash_profile…...
C#中的各种画刷, PathGradientBrush、线性渐变(LinearGradientBrush)和径向渐变的区别
在C#中,画刷(Brush)是用来填充图形(如形状或文本)内部区域的对象。在.NET框架中,画刷是System.Drawing命名空间的一部分,通常用于GDI绘图操作。以下是一些常用的画刷类型: SolidBru…...
如何在Mac中修改pip的镜像源
一. 修改步骤 进入命令行 进入到用户根目录 cd ~/在用户根目录下创建 .pip 文件夹 mkdir .pip进入到 ~/.pip 文件夹内 cd ~/.pip创建 pip.conf 文件 vim pip.conf在 pip.conf 文件中添加清华大学的镜像源,如下: [global] index-urlhttps://pypi.tuna.ts…...

MySQL你必须知道的事
文章目录 前言一、InnoDB的数据页,和B树的关系?二、为什么InnoDB三层B树可以存2000w数据三、什么是InnoDB的页分裂和页合并四、什么是回表?怎么减少回表的次数?什么是覆盖索引,索引下推?覆盖索引索引下推总…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...

对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...

Mysql故障排插与环境优化
前置知识点 最上层是一些客户端和连接服务,包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念,为通过安全认证接入的客户端提供线程。同样在该层上可…...

在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!
多连接 BLE 怎么设计服务不会乱?分层思维来救场! 作者按: 你是不是也遇到过 BLE 多连接时,调试现场像网吧“掉线风暴”? 温度传感器连上了,心率带丢了;一边 OTA 更新,一边通知卡壳。…...