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

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...