当前位置: 首页 > 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编译…...

Rusted PackFile Manager:从零开始打造你的Total War模组

Rusted PackFile Manager&#xff1a;从零开始打造你的Total War模组 【免费下载链接】rpfm Rusted PackFile Manager (RPFM) is a... reimplementation in Rust and Qt5 of PackFile Manager (PFM), one of the best modding tools for Total War Games. 项目地址: https://…...

3分钟快速优化Windows性能:Mem Reduct系统优化工具终极指南

3分钟快速优化Windows性能&#xff1a;Mem Reduct系统优化工具终极指南 【免费下载链接】memreduct Lightweight real-time memory management application to monitor and clean system memory on your computer. 项目地址: https://gitcode.com/gh_mirrors/me/memreduct …...

AssetRipper架构深度解析:Unity资源逆向工程的完整技术方案

AssetRipper架构深度解析&#xff1a;Unity资源逆向工程的完整技术方案 【免费下载链接】AssetRipper GUI Application to work with engine assets, asset bundles, and serialized files 项目地址: https://gitcode.com/GitHub_Trending/as/AssetRipper AssetRipper是…...

Conan实战指南:从零搭建私有C++依赖仓库

1. 为什么C团队需要私有依赖仓库 在C开发领域&#xff0c;依赖管理一直是个令人头疼的问题。我见过太多团队在项目启动时&#xff0c;把大量时间花在配置第三方库上。有人直接把第三方库源码塞进项目目录&#xff0c;有人要求每个开发者手动安装系统级依赖&#xff0c;还有人写…...

卷积神经网络原理详解:使用Phi-3-mini进行交互式学习与代码生成

卷积神经网络原理详解&#xff1a;使用Phi-3-mini进行交互式学习与代码生成 1. 引言&#xff1a;为什么选择CNN作为深度学习入门 卷积神经网络&#xff08;CNN&#xff09;是计算机视觉领域的基石技术&#xff0c;从人脸识别到自动驾驶都离不开它。但对于初学者来说&#xff0c…...

Pixel Mind Decoder 性能调优教程:解决GPU显存不足与推理加速

Pixel Mind Decoder 性能调优教程&#xff1a;解决GPU显存不足与推理加速 1. 为什么需要性能调优 当你第一次把Pixel Mind Decoder模型跑起来时&#xff0c;可能会遇到两个让人头疼的问题&#xff1a;要么显存不够用导致程序崩溃&#xff0c;要么推理速度慢得像蜗牛爬。这种情…...

ThinkPHP 8+redis的生命周期的庖丁解牛

它的本质是&#xff1a;PHP 进程&#xff08;客户端&#xff09;通过 TCP 套接字与 Redis 守护进程&#xff08;服务端&#xff09;建立连接&#xff0c;发送基于 RESP 协议的指令&#xff0c;接收二进制响应&#xff0c;并将结果映射回 PHP 变量的全过程。在 TP8 中&#xff0…...

5分钟快速上手:XXMI启动器统一游戏模组管理平台完全指南

5分钟快速上手&#xff1a;XXMI启动器统一游戏模组管理平台完全指南 【免费下载链接】XXMI-Launcher Modding platform for GI, HSR, WW and ZZZ 项目地址: https://gitcode.com/gh_mirrors/xx/XXMI-Launcher 还在为多款二次元游戏的模组管理而烦恼吗&#xff1f;XXMI启…...

3D打印机 爱乐酷CC2 SSH后台远程登录root账号密码

机型&#xff1a;Elegoo Centauri Carbon 2当前固件版本&#xff1a;V01.03.01.89SSH地址&#xff1a;打印机IP地址&#xff0c;例如192.168.31.101SSH端口&#xff1a;22SSH账号&#xff1a;rootSSH密码&#xff1a;MTY4ODE2机器设置->日志导出&#xff0c;导出到U盘的zip压…...

达摩院春联AI实战落地:中小企业春节营销内容智能生产方案

达摩院春联AI实战落地&#xff1a;中小企业春节营销内容智能生产方案 1. 引言&#xff1a;当春节营销遇上AI 春节&#xff0c;是中国人最重要的节日&#xff0c;也是商家营销的黄金时段。对于中小企业来说&#xff0c;如何在这个节点高效、低成本地创作出有年味、有创意的营销…...