【Leetcode】2009. 使数组连续的最少操作数
文章目录
- 题目
- 思路
- 代码
- 复杂度分析
- 时间复杂度
- 空间复杂度
- 结果
- 总结
题目
题目链接🔗
给你一个整数数组 n u m s nums nums 。每一次操作中,你可以将 n u m s nums nums 中 任意 一个元素替换成 任意 整数。
如果 n u m s nums nums 满足以下条件,那么它是 连续的 :
n u m s nums nums 中所有元素都是 互不相同 的。
n u m s nums nums 中 最大 元素与 最小 元素的差等于 n u m s . l e n g t h − 1 nums.length - 1 nums.length−1 。
比方说, n u m s = [ 4 , 2 , 5 , 3 ] nums = [4, 2, 5, 3] nums=[4,2,5,3] 是 连续的 ,但是 n u m s = [ 1 , 2 , 3 , 5 , 6 ] nums = [1, 2, 3, 5, 6] nums=[1,2,3,5,6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1:
输入:nums = [4,2,5,3]
输出:0
解释:nums 已经是连续的了。
示例 2:
输入:nums = [1,2,3,5,6]
输出:1
解释:一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ,是连续数组。
示例 3:
输入:nums = [1,10,100,1000]
输出:3
解释:一个可能的解是:
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ,是连续数组。
提示:
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105
- 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \leq nums[i] \leq 10^9 1≤nums[i]≤109
思路
- 对数组进行排序,这样相邻的元素就可以保证是连续的。然后去除重复元素,确保数组中的元素互不相同。对于数组中的每个元素 n u m s [ i ] nums[i] nums[i],我们需要找到满足条件的最大元素 n u m s [ j ] nums[j] nums[j],使得 n u m s [ j ] − n u m s [ i ] = n u m s . s i z e ( ) − 1 nums[j] - nums[i] = nums.size() - 1 nums[j]−nums[i]=nums.size()−1。
- 使用二分查找来寻找满足条件的最大元素。具体地,可以遍历数组中的每个元素 n u m s [ i ] nums[i] nums[i],然后使用二分查找找到最大值不超过 n u m s [ i ] + n u m s . s i z e ( ) − 1 nums[i] + nums.size() - 1 nums[i]+nums.size()−1 的元素,即 n u m s [ j ] ≤ n u m s [ i ] + n u m s . s i z e ( ) − 1 nums[j] \leq nums[i] + nums.size() - 1 nums[j]≤nums[i]+nums.size()−1。
- 对于每个元素 n u m s [ i ] nums[i] nums[i],可以计算需要的操作次数为 n u m s . s i z e ( ) − ( j − i + 1 ) nums.size() - (j - i + 1) nums.size()−(j−i+1),其中 j j j 是满足条件的最大元素的下标。
代码
class Solution {
public:int minOperations(vector<int>& nums) {ranges::sort(nums);int n = nums.size();nums.resize(unique(nums.begin(), nums.end()) - nums.begin());int m = nums.size();int res = INT_MAX;for(int i = 0; i < m; i++) {int x = nums[i];int y = x + n - 1;int l = i, r = m - 1;while(l < r) {int mid = (l + r + 1) / 2;if(nums[mid] > y) r = mid - 1;else l = mid;}res = min(res, n - (l - i + 1));} return res;}
};
复杂度分析
时间复杂度
O ( n log n ) O(n \log n) O(nlogn)
空间复杂度
O ( 1 ) O(1) O(1)
结果
总结
关键在于如何通过排序和遍历找到满足条件的最小操作次数。我们通过排序数组并去除重复元素,然后对每个元素进行遍历,通过二分查找找到最大值不超过 y y y 的元素,并计算需要的操作次数,最后选择操作次数最小的那个作为结果。
相关文章:

【Leetcode】2009. 使数组连续的最少操作数
文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目 题目链接🔗 给你一个整数数组 n u m s nums nums 。每一次操作中,你可以将 n u m s nums nums 中 任意 一个元素替换成 任意 整数。 如果 n u m s nums nums 满足以下条件&…...

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】
LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】 题目描述:解题思路一:哈希表记录出现次数,然后用最小堆取,因为每次都是弹出最小的,剩下的一定是K…...
K8S Deployment HA
文章目录 K8S Deployment HA1.机器规划2.前期准备2.1 安装ansible2.2 修改 hostname2.3 配置免密2.4 时间同步2.5 系统参数调整2.6 安装 Docker2.7 部署 HaproxyKeepalived 3. 部署 K8S3.1 安装 k8s命令3.2 k8s初始化3.3 添加其他master节点3.4 添加 Node节点3.5 安装 CNI3.6 查…...
【Linux】linux 在指定根目录下,查找wav文件并删除
要在Linux的指定根目录下查找.wav文件并删除它们,您可以使用find命令结合-exec选项来执行删除操作。请注意,这个操作是不可逆的,所以在执行之前请确保您知道自己在做什么,并且已经备份了重要数据。 以下是一个示例命令࿰…...

三、SpringBoot3 整合 SpringMVC
本章概要 实现过程web 相关配置静态资源处理自定义拦截器(SpringMVC 配置) 3.1 实现过程 创建程序引入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www…...

设计模式之解释器模式(上)
解释器模式 1)概述 1.定义 定义一个语言的文法,并且建立一个解释器来解释该语言中的句子,这里的“语言”是指使用规定格式和语法的代码。 2.结构图 3.角色 AbstractExpression(抽象表达式):在抽象表达…...
[23年蓝桥杯] 买二赠一
题目描述 【问题描述】 某商场有 N 件商品,其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二 赠一” 的优惠活动,具体规则是: 每购买 2 件商品,假设其中较便宜的价格是 P (如果两件商品价格一样, 则…...
PgSQL的with as语法
returning 返回的这一些字段,然后进行汇总为remove_alarms 然后select一下remove_alarms 出来的数据然后保存到tb_alarm_his 里面 with remove_alarms as( delete fromtb_alarm whereid in (508) returning 0,now(),admin,alarmadvice,alarmadvicecn,alarmarises…...
六、c++代码中的安全风险-fopen
(misc) fopen: Check when opening files - can an attacker redirect it (via symlinks), force the opening of special file type (e.g., device files), move things around to create a race condition, control its ancestors, or change its contents? (CWE-362). 为…...

uniapp项目问题及解决(前后端互联)
1.路由跳转的问题 uni.navigateTo() 保留当前页面,跳转到应用内的某个页面,使用uni.navigateBack可以返回到原页面 uni.redirectTo() 关闭当前页面,跳转到应用内的某个页面。 uni.reLaunch&…...

面试算法-154-搜索二维矩阵 II
题目 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1: 输入:matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,…...
Java中Stream流介绍
Java 8引入的Stream API是Java中处理集合的一种高效方式,它提供了一种高级的迭代方式,允许你以声明式方式处理数据。Stream API可以对数据执行复杂的查询操作,而不需要编写冗长且复杂的循环语句。下面是一些使用Stream API的常见场景和示例&a…...
深度学习的层、算子和函数空间
目录 一、层、算子和函数空间概念 二、层(Layers) 三、算子(Operators) 3.1常见算子 3.2常见算子的性质 四、函数空间(Function Space) 一、层、算子和函数空间概念 层(Layers)…...

Pillow教程11:九宫格切图的实现方法(安排!!!)
---------------Pillow教程集合--------------- Python项目18:使用Pillow模块,随机生成4位数的图片验证码 Python教程93:初识Pillow模块(创建Image对象查看属性图片的保存与缩放) Pillow教程02:图片的裁…...

Macos 部署自己的privateGpt(2024-0404)
Private Chatgpt 安装指引 https://docs.privategpt.dev/installation/getting-started/installation#base-requirements-to-run-privategpt 下载源码 git clone https://github.com/imartinez/privateGPT cd privateGPT安装软件 安装: Homebrew /bin/bash -c…...
先安装CUDA后安装Visual Studio的额外配置
VS新建项目中增加CUDA选项 以vs2019 cuda 11.3为例 关闭vs2019解压cuda的windows安装包cuda_11.3.0_465.89_win10.exe进入路径cuda_11.3.0_465.89_win10\visual_studio_integration\CUDAVisualStudioIntegration\extras\visual_studio_integration\CudaProjectVsWizards\拷贝…...
2024 蓝桥打卡Day35
20240407蓝桥杯备赛 1、学习蓝桥云课省赛冲刺课 【3-搜索算法】【4-枚举与尺度法】2、学习蓝桥云课Java省赛无忧班 【1-语言基础】3、代码练习数字反转数字反转优化算法sort排序相关String字符串相关StringBuilder字符串相关HashSet相关 1、学习蓝桥云课省赛冲刺课 【3-搜索算法…...

【Java】单例模式
单例模式是面试中常考的设计模式之一 在面试中,面试官常常会要求写出两种类型的单例模式并解释原理 本文中,将从0到1的介绍单例模式究竟是什么 文章目录 ✍一、什么是设计模式?✍二、单例模式是什么?✍三、单例模式的类型**1.饿汉…...

Linux|从 STDIN 读取 Awk 输入
简介 在之前关于 Awk 工具的系列文章中,主要探讨了如何从文件中读取数据。但如果你希望从标准输入(STDIN)中读取数据,又该如何操作呢? 在本文中,将介绍几个示例,展示如何使用 Awk 来过滤其他命令…...
关于K8S集群中maste节点r和worker节点的20道面试题
1. 什么是Kubernetes(K8S)? Kubernetes(通常简称为K8S)是一种开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是Kubernetes的一些核心特性和优势: 自动化部署和扩展&…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...