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

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个数对&#xff0c;使差值绝对值的和最小。 思路&#xff1a; 最小差值应该是数值相近的一对数之间产生&#xff0c;让数值相近的数字尽量靠在一起方便计算&#xff0c;所以需要排序。 这里不去直接考虑一对对的数字&#xff0c;而是直接考虑差值的取值。 …...

npm install 安装慢的问题处理

原因 npm install 默认使用的安装镜像时国外的镜像&#xff0c;国内使用会受到网络的限制。 解决方案 更换网络更换npm的安装镜像为国内&#xff0c;比如&#xff1a; npm config set registry https://registry.npm.taobao.org...

【JAVA】七大排序算法(图解)

稳定性&#xff1a; 待排序的序列中若存在值相同的元素&#xff0c;经过排序之后&#xff0c;相等元素的先后顺序不发生改变&#xff0c;称为排序的稳定性。 思维导图&#xff1a; &#xff08;排序名称后面蓝色字体为时间复杂度和稳定性&#xff09; 1.直接插入排序 核心思…...

UNIX 系统概要

UNIX 家族UNIX 家谱家族后起之秀 LinuxUNIX vs LinuxUNIX/Linux 应用领域 UNIX 操作系统诞生与发展UNIX 操作系统概要内核常驻模块shell虚拟计算机特性 其他操作系统 LinuxRichard StallmanGNU 项目FSF 组织GPL 协议Linus Torvalds UNIX 家族 有人说&#xff0c;这个世界上只有…...

Unity 基础函数

Mathf&#xff1a; //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; …...

【学习】若依源码(前后端分离版)之 “ 上传图片功能实现”

大型纪录片&#xff1a;学习若依源码&#xff08;前后端分离版&#xff09;之 “ 上传图片功能实现” 前言前端部分后端部分结语 前言 图片上传也基本是一个项目的必备功能了&#xff0c;所以今天和大家分享一下我最近在使用若依前后端分离版本时&#xff0c;如何实现图片上传…...

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 相关框架事务开启方式

前言 对于框架而言&#xff0c;各式API接口少不了伴随着事务的场景&#xff0c;下面就列举常用框架的事务开启方法 一、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按需引入 说明&#xff1a;为了输入时候有提示&#xff0c;建…...

Python做一个绘图系统3:从文本文件导入数据并绘图

文章目录 导入数据文件对话框修改绘图逻辑源代码 Python绘图系统系列&#xff1a;将matplotlib嵌入到tkinter 简单的绘图系统 导入数据 单纯从作图的角度来说&#xff0c;更多情况是已经有了一组数据&#xff0c;然后需要将其绘制。这组数据可能是txt格式的&#xff0c;也可能…...

flutter开发实战-获取Widget的大小及位置

flutter开发实战-获取Widget的大小及位置 最近开发过程中需要获取Widget的大小及位置&#xff0c;这时候就需要使用到了GlobalKey了和WidgetsBinding.instance.addPostFrameCallback了 一、addPostFrameCallback 该函数的作用&#xff1a; flutter中的界面组件Widget每一帧…...

软件测试工程师面试如何描述自动化测试是怎么实现的?

软件测试工程师面试的时候&#xff0c;但凡简历中有透露一点点自己会自动化测试的技能点的描述&#xff0c;都会被面试官问&#xff0c;那你结合你的测试项目说说自动化测试是怎么实现的&#xff1f;一到这里&#xff0c;很多网友&#xff0c;包括我的学生&#xff0c;也都一脸…...

Qt5兼容使用之前Qt4接口 intersect接口

1. 问题 项目卡中遇到编译报错&#xff0c; 错误 C2039 “intersect”: 不是“QRect”的成员 。 2. 排查过程 排查到依赖的第三方代码&#xff0c;使用 intersect 接口&#xff0c; 跟踪排查到头文件中使用了***#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 /*********************************************************************说明:试着扩充这个程序的内容&#xff1a;&#xff08;1&#xff09;要求用户同时输…...

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插件&#xff1a; File--->Setting---->plugins,在输入框中输入scala&#xff0c;然后点击“Install”即可安装scala&#xff0c;需要稍微等待几分钟。 2 创建项目&#xff1a; File ---->new---->project-----Maven--->Next----输入名称(test…...

LT8711UXD 是一款高性能双通道 Type-C/DP1.4 至 HDMI2.0 转换器

LT8711UXD 1.描述 LT8711UXD是一款高性能的双车道TypeC/DP1.4到HDMI2.0转换器&#xff0c;设计用于将USB Type-C源或DP1.4源连接到HDMI2.0接收器。LT8711UXD集成了一个DP1.4兼容的接收机&#xff0c;和一个HDMI2.0兼容的发射机。此外&#xff0c;还包括两个CC控制器&#xff0…...

Android APK体积优化(瘦身)

1、基础知识&#xff1a; 1.1 apk结构 lib &#xff1a;存放so文件&#xff0c;对应不同的cpu架构 res &#xff1a;资源文件&#xff0c;layout、drawable等&#xff0c;经过aapt编译 assets &#xff1a;资源文件&#xff0c;不经过aapt编译 classes.dex &#xff1a;dx编译…...

MedGemma-X新手教程:一键搭建AI放射科数字助手

MedGemma-X新手教程&#xff1a;一键搭建AI放射科数字助手 1. 为什么你需要一个能“看懂”X光片的AI助手&#xff1f; 想象一下这个场景&#xff1a;深夜的放射科值班室&#xff0c;你面前堆着几十张待阅的胸片&#xff0c;眼睛已经有些干涩。其中一张片子&#xff0c;右肺中…...

终极指南:ESLyric-LyricsSource三大逐字歌词格式深度解析与实战部署

终极指南&#xff1a;ESLyric-LyricsSource三大逐字歌词格式深度解析与实战部署 【免费下载链接】ESLyric-LyricsSource Advanced lyrics source for ESLyric in foobar2000 项目地址: https://gitcode.com/gh_mirrors/es/ESLyric-LyricsSource ESLyric-LyricsSource是专…...

复旦微FM33 MCU 底层开发实战——从寄存器到外设精通

1. 初识复旦微FM33系列MCU 第一次拿到复旦微FM33LC0XX开发板时&#xff0c;我和大多数嵌入式开发者一样&#xff0c;习惯性地打开标准外设库开始写代码。但很快发现&#xff0c;当需要实现特定功能或优化性能时&#xff0c;库函数的封装反而成了障碍。这就像开车时只能使用自动…...

优酷网页截图黑屏问题解析:探索浏览器图形服务API的幕后机制

1. 优酷网页截图黑屏现象解析 最近有不少用户反馈&#xff0c;在优酷网页观看视频时尝试截图&#xff0c;结果保存的图片却是全黑的。这个问题看似简单&#xff0c;背后却涉及到浏览器图形渲染的复杂机制。作为一名长期研究浏览器底层技术的开发者&#xff0c;我发现这个问题其…...

[特殊字符]️ MusePublicGPU效率提升:EulerAncestral调度器加速原理与调参

&#x1f3db; MusePublicGPU效率提升&#xff1a;EulerAncestral调度器加速原理与调参 1. 为什么是EulerAncestral&#xff1f;——它不是最快的&#xff0c;但最稳最出片 你有没有遇到过这样的情况&#xff1a;明明显卡够用&#xff0c;生成一张图却要等一分多钟&#xff1…...

HTTP接口设计进阶技巧:http-api-guide高级应用解析

HTTP接口设计进阶技巧&#xff1a;http-api-guide高级应用解析 【免费下载链接】http-api-guide 项目地址: https://gitcode.com/gh_mirrors/ht/http-api-guide 在API开发领域&#xff0c;设计一套规范、高效且易于维护的HTTP接口至关重要。http-api-guide作为一份全面…...

零基础入门YOLOv10:用官方镜像3步搞定工业缺陷识别

零基础入门YOLOv10&#xff1a;用官方镜像3步搞定工业缺陷识别 1. YOLOv10镜像快速上手 1.1 为什么选择YOLOv10官版镜像 YOLOv10官版镜像是一个开箱即用的深度学习环境&#xff0c;特别适合想要快速上手目标检测的新手开发者。这个镜像已经预装了所有必要的软件和依赖项&…...

[特殊字符]Liberty Parser 可视化工具

一个纯前端、开箱即用的 .lib 文件解析 可视化分析工具。 &#x1f5bc;️ 工具界面一览 &#xff08;这里你可以放截图&#xff0c;效果很好&#xff09; 工具支持&#xff1a; &#x1f4c2; 直接上传 .lib 文件&#x1f50d; 实时筛选 cell / pin&#x1f4ca; 可视化展…...

Windows下OpenClaw全攻略:千问3.5-35B-A3B-FP8接入与飞书联动

Windows下OpenClaw全攻略&#xff1a;千问3.5-35B-A3B-FP8接入与飞书联动 1. 为什么选择OpenClaw作为Windows自动化助手 去年我接手了一个跨部门协作项目&#xff0c;每天需要在飞书、Excel和多个网页工具间反复切换操作。当我在凌晨三点第七次手动整理数据时&#xff0c;突然…...

ERTEC 系列 PROFINET 芯片级硬件过滤器分析仓

一、语言特性&#xff1a;Java 26 与模式匹配进化 1.1 Java 26 语言级别支持 IDEA 2026.1 EAP 最引人注目的变化之一&#xff0c;就是新增 Java 26 语言级别支持。这意味着开发者可以提前体验和测试即将在 JDK 26 中正式发布的语言特性。 其中最重要的变化是对 JEP 530 的全…...