leetcode 2616. 最小化数对的最大差值

在数组nums中找到p个数对,使差值绝对值的和最小。
思路:
最小差值应该是数值相近的一对数之间产生,让数值相近的数字尽量靠在一起方便计算,所以需要排序。
这里不去直接考虑一对对的数字,而是直接考虑差值的取值。
用binary search搜索一个差值。
左边界是0,右边界就是nums中的最大值 - 最小值(nums排序后最右边数字 - 最左边数字)。
确定mid = 差值,那么一对数字的差的绝对值如果 <= 这个差值,就说明满足,
遍历数组nums, 计算满足 <= 差值的数字有多少对,记为cnt对,
如果cnt >= p, 说明差值在mid内的数字对能达到p个,可以进一步缩小差值,right= mid.
反之需要left = mid+1.
class Solution {int n = 0;public int minimizeMax(int[] nums, int p) {n = nums.length;Arrays.sort(nums);int left = 0;int right = nums[n-1] - nums[0];while(left < right) {int mid = left + (right - left) / 2;if(canMakePairs(mid, nums, p)) {right = mid;} else {left = mid + 1;}}return left;}boolean canMakePairs(int mid, int[] nums, int p) {int cnt = 0;for(int i = 0; i < n-1 && cnt < p;i++){ //在这里限制cnt<p,因为p可以是0if(nums[i+1] - nums[i] <= mid) {cnt ++;i ++; //加上for里面的i++,相当于i向右移动2位}}return cnt >= p;}
}
相关文章:
leetcode 2616. 最小化数对的最大差值
在数组nums中找到p个数对,使差值绝对值的和最小。 思路: 最小差值应该是数值相近的一对数之间产生,让数值相近的数字尽量靠在一起方便计算,所以需要排序。 这里不去直接考虑一对对的数字,而是直接考虑差值的取值。 …...
npm install 安装慢的问题处理
原因 npm install 默认使用的安装镜像时国外的镜像,国内使用会受到网络的限制。 解决方案 更换网络更换npm的安装镜像为国内,比如: npm config set registry https://registry.npm.taobao.org...
【JAVA】七大排序算法(图解)
稳定性: 待排序的序列中若存在值相同的元素,经过排序之后,相等元素的先后顺序不发生改变,称为排序的稳定性。 思维导图: (排序名称后面蓝色字体为时间复杂度和稳定性) 1.直接插入排序 核心思…...
UNIX 系统概要
UNIX 家族UNIX 家谱家族后起之秀 LinuxUNIX vs LinuxUNIX/Linux 应用领域 UNIX 操作系统诞生与发展UNIX 操作系统概要内核常驻模块shell虚拟计算机特性 其他操作系统 LinuxRichard StallmanGNU 项目FSF 组织GPL 协议Linus Torvalds UNIX 家族 有人说,这个世界上只有…...
Unity 基础函数
Mathf: //1.π-PI print(Mathf.PI); //2.取绝对值-Abs print(Mathf.Abs(-10)); print(Mathf.Abs(-20)); print(Mathf.Abs(1)); //3.向上取整-Ce il To In t float f 1.3f; int i (int)f; …...
【学习】若依源码(前后端分离版)之 “ 上传图片功能实现”
大型纪录片:学习若依源码(前后端分离版)之 “ 上传图片功能实现” 前言前端部分后端部分结语 前言 图片上传也基本是一个项目的必备功能了,所以今天和大家分享一下我最近在使用若依前后端分离版本时,如何实现图片上传…...
vue3 excel 导出功能
1.安装 xlsx 库 npm install xlsx2.创建导出函数 src/utils/excelUtils.js import * as XLSX from xlsx;const exportToExcel (fileName, datas, sheetNames) > {// 创建工作簿const wb XLSX.utils.book_new()for (let i 0; i < datas.length; i) {let data datas…...
python 相关框架事务开启方式
前言 对于框架而言,各式API接口少不了伴随着事务的场景,下面就列举常用框架的事务开启方法 一、Django import traceback from django.db import transaction from django.contrib.auth.models import User try:with transaction.atomic(): # 在with…...
vue使用ElementUI
1.安装 npm i element-ui -S 2.引入 2.1完整引入 import Vue from vue; import ElementUI from element-ui; import element-ui/lib/theme-chalk/index.css; import App from ./App.vue;Vue.use(ElementUI); 2.2按需引入 说明:为了输入时候有提示,建…...
Python做一个绘图系统3:从文本文件导入数据并绘图
文章目录 导入数据文件对话框修改绘图逻辑源代码 Python绘图系统系列:将matplotlib嵌入到tkinter 简单的绘图系统 导入数据 单纯从作图的角度来说,更多情况是已经有了一组数据,然后需要将其绘制。这组数据可能是txt格式的,也可能…...
flutter开发实战-获取Widget的大小及位置
flutter开发实战-获取Widget的大小及位置 最近开发过程中需要获取Widget的大小及位置,这时候就需要使用到了GlobalKey了和WidgetsBinding.instance.addPostFrameCallback了 一、addPostFrameCallback 该函数的作用: flutter中的界面组件Widget每一帧…...
软件测试工程师面试如何描述自动化测试是怎么实现的?
软件测试工程师面试的时候,但凡简历中有透露一点点自己会自动化测试的技能点的描述,都会被面试官问,那你结合你的测试项目说说自动化测试是怎么实现的?一到这里,很多网友,包括我的学生,也都一脸…...
Qt5兼容使用之前Qt4接口 intersect接口
1. 问题 项目卡中遇到编译报错, 错误 C2039 “intersect”: 不是“QRect”的成员 。 2. 排查过程 排查到依赖的第三方代码,使用 intersect 接口, 跟踪排查到头文件中使用了***#if QT_DEPRECATED_SINCE(5, 0)*** #if QT_DEPRECATED_SINCE…...
【云原生】Kubernetes节点亲和性分配 Pod
目录 1 给节点添加标签 2 根据选择节点标签指派 pod 到指定节点[nodeSelector] 3 根据节点名称指派 pod 到指定节点[nodeName] 4 根据 亲和性和反亲和性 指派 pod 到指定节点 5 节点亲和性权重 6 pod 间亲和性和反亲和性及权重 7 污点和容忍度 8 Pod 拓扑分布约束 官方…...
【Essential C++课后练习】纯代码(更新中)
文章目录 第一章 C编程基础1.41.51.61.71.8 第二章 面向过程的编程风格2.12.22.32.42.52.6 第一章 C编程基础 1.4 /*********************************************************************说明:试着扩充这个程序的内容:(1)要求用户同时输…...
C#仿热血江湖GClass
目录 1 C#仿热血江湖GClass 1.1 GClass32 1.2 method_4 1.3 smethod_0 C#仿热血江湖GClass public class GClass32 { private byte[] byte_0;...
[SQL智慧航行者] - 用户购买商品推荐
话不多说, 先看数据表信息. 数据表信息: employee 表, 包含所有员工信息, 每个员工有其对应的 id, salary 和 departmentid. --------------------------------- | id | name | salary | departmentid | --------------------------------- | 1 | Joe | 70000 | 1 …...
Idea配置Scala开发环境
1.首先安装scala插件: File--->Setting---->plugins,在输入框中输入scala,然后点击“Install”即可安装scala,需要稍微等待几分钟。 2 创建项目: File ---->new---->project-----Maven--->Next----输入名称(test…...
LT8711UXD 是一款高性能双通道 Type-C/DP1.4 至 HDMI2.0 转换器
LT8711UXD 1.描述 LT8711UXD是一款高性能的双车道TypeC/DP1.4到HDMI2.0转换器,设计用于将USB Type-C源或DP1.4源连接到HDMI2.0接收器。LT8711UXD集成了一个DP1.4兼容的接收机,和一个HDMI2.0兼容的发射机。此外,还包括两个CC控制器࿰…...
Android APK体积优化(瘦身)
1、基础知识: 1.1 apk结构 lib :存放so文件,对应不同的cpu架构 res :资源文件,layout、drawable等,经过aapt编译 assets :资源文件,不经过aapt编译 classes.dex :dx编译…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...
【2D与3D SLAM中的扫描匹配算法全面解析】
引言 扫描匹配(Scan Matching)是同步定位与地图构建(SLAM)系统中的核心组件,它通过对齐连续的传感器观测数据来估计机器人的运动。本文将深入探讨2D和3D SLAM中的各种扫描匹配算法,包括数学原理、实现细节以及实际应用中的性能对比,特别关注…...
Spring是如何实现无代理对象的循环依赖
无代理对象的循环依赖 什么是循环依赖解决方案实现方式测试验证 引入代理对象的影响创建代理对象问题分析 源码见:mini-spring 什么是循环依赖 循环依赖是指在对象创建过程中,两个或多个对象相互依赖,导致创建过程陷入死循环。以下通过一个简…...
