当前位置: 首页 > 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 为点的数量。主要为哈希表的开销。

相关文章:

直线上最多的点数

优质博文&#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; 输入&am…...

经济管理专业数据库介绍

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

【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幸存的最古老的两个命令行工具&#xff0c;其实我从来不认为Exp/Imp是一种好的备份方式&#xff0c;正确的说法是Exp/Imp只能是一个好的转储工具&#xff0c;特别是在小型数据库的转储&#xff0c;表空间的迁移&#xff0c;表的抽取&#xff0c;检测逻辑和物理…...

中国各银行流动性比例数据(2000-2022年)

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

MACOS安装配置前端开发环境

官网下载安装Mac版本的谷歌浏览器以及VS code代码编辑器&#xff0c;还有在App Store中直接安装Xcode&#xff08;里面自带git&#xff09;&#xff1b; node.js版本管理器nvm的下载安装如下&#xff1a; 参考B站&#xff1a;https://www.bilibili.com/video/BV1M54y1N7fx/?sp…...

Docker 配置国内镜像源

由于 GFW 的原因&#xff0c;在下载镜像的时候&#xff0c;经常会出现下载失败的情况&#xff0c;此时就可以使用国内的镜像源。 什么是镜像源&#xff1a;简单来说就是某个组织&#xff08;学校、公司、甚至是个人&#xff09;先通过某种手段将国外的镜像下载下来&#xff0c;…...

AI模块在人工智能中扮演着什么样的角色

AI模块在人工智能&#xff08;AI&#xff09;中扮演着核心和关键的角色。它们是构成AI系统的基础单元&#xff0c;负责实现AI系统的各种智能功能。以下是AI模块在人工智能中扮演的具体角色&#xff1a; 功能实现的核心&#xff1a;AI模块集成了实现特定智能功能所需的算法、数据…...

VM Workstation虚拟机AlmaLinux 9.4操作系统安装(桌面版安装详细教程)(宝塔面板的安装),填补CentOS终止支持维护的空白

目录 AlmaLinux介绍 AlmaLinux操作系统的安装 1、下载镜像文件 2、新建虚拟机 &#xff08;1&#xff09;点击创建新的虚拟机 &#xff08;2&#xff09;打开虚拟机向导后&#xff0c;选择“自定义”安装&#xff0c;然后点击“下一步” &#xff08;3&#xff09;选择虚…...

【学习笔记】卫星通信NTN 3GPP标准化进展分析(三)- 3GPP Release17 内容

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

【SQL】常见语句合集

SQL常见语句合集 一. 新建表1.1 语句1.2 结果 二. 新增数据2.1 语句2.2 结果 三. 新增字段列3.1 语句3.2 结果3.3 扩展 四. 更新指定数据4.1 语句4.2 结果 五. 更新指定列5.1 语句&#xff08;长度&#xff09; 六. 删除字段列6.1 语句 七. 删除指定数据7.1 语句 八. 查询 一. …...

Cozer必备!一站式解锁扣子全网最全插件集锦(三)

俗话说&#xff0c;工欲善其事必先利其器&#xff01; 用过Coze的朋友都知道&#xff0c;插件在Coze里的重要性。插件库就相当于武器库&#xff0c;一个好的插件&#xff0c;就相当于一件趁手的兵器&#xff0c;可以让你事半功倍&#xff01; 程哥精心整理了Coze最常用和好用…...

1-2宿主环境

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

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&#xff0c;aa 与 dd&#xff0c;表示一个项数为 nn 的等差数列&#xff0c;首项为 aa&#xff0c;公差为 dd。 请统计&#xff0c;从这个等差数列中有多少数字是素数 输入格式 三个整数&#xff1a; nn&#xff0c;aa 与 dd 输出格式 单个整数…...

VR虚拟展厅的应用场景有哪些?

虚拟展厅作为一种利用虚拟现实技术构建的三维展示空间&#xff0c;其应用场景广泛且多样。视创云展为企业虚拟展厅搭建提供技术支持。以下是一些主要的应用场景&#xff1a; 1. 博物馆和艺术展览 文物保护与展示&#xff1a; 在博物馆中&#xff0c;为了保护珍贵的文物和艺术…...

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#中&#xff0c;画刷&#xff08;Brush&#xff09;是用来填充图形&#xff08;如形状或文本&#xff09;内部区域的对象。在.NET框架中&#xff0c;画刷是System.Drawing命名空间的一部分&#xff0c;通常用于GDI绘图操作。以下是一些常用的画刷类型&#xff1a; SolidBru…...

如何在Mac中修改pip的镜像源

一. 修改步骤 进入命令行 进入到用户根目录 cd ~/在用户根目录下创建 .pip 文件夹 mkdir .pip进入到 ~/.pip 文件夹内 cd ~/.pip创建 pip.conf 文件 vim pip.conf在 pip.conf 文件中添加清华大学的镜像源&#xff0c;如下&#xff1a; [global] index-urlhttps://pypi.tuna.ts…...

MySQL你必须知道的事

文章目录 前言一、InnoDB的数据页&#xff0c;和B树的关系&#xff1f;二、为什么InnoDB三层B树可以存2000w数据三、什么是InnoDB的页分裂和页合并四、什么是回表&#xff1f;怎么减少回表的次数&#xff1f;什么是覆盖索引&#xff0c;索引下推&#xff1f;覆盖索引索引下推总…...

c#开发AI模型对话

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

以光量子为例,详解量子获取方式

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

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

对象回调初步研究

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

Mysql故障排插与环境优化

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

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...