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

【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.length1
比方说, 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 1nums.length105
  • 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \leq nums[i] \leq 10^9 1nums[i]109

思路

  1. 对数组进行排序,这样相邻的元素就可以保证是连续的。然后去除重复元素,确保数组中的元素互不相同。对于数组中的每个元素 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
  2. 使用二分查找来寻找满足条件的最大元素。具体地,可以遍历数组中的每个元素 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
  3. 对于每个元素 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()(ji+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. 使数组连续的最少操作数

文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目 题目链接&#x1f517; 给你一个整数数组 n u m s nums nums 。每一次操作中&#xff0c;你可以将 n u m s nums nums 中 任意 一个元素替换成 任意 整数。 如果 n u m s nums nums 满足以下条件&…...

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆&#xff08;优先队列&#xff09;】 题目描述&#xff1a;解题思路一&#xff1a;哈希表记录出现次数&#xff0c;然后用最小堆取&#xff0c;因为每次都是弹出最小的&#xff0c;剩下的一定是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文件并删除它们&#xff0c;您可以使用find命令结合-exec选项来执行删除操作。请注意&#xff0c;这个操作是不可逆的&#xff0c;所以在执行之前请确保您知道自己在做什么&#xff0c;并且已经备份了重要数据。 以下是一个示例命令&#xff0…...

三、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&#xff09;概述 1.定义 定义一个语言的文法&#xff0c;并且建立一个解释器来解释该语言中的句子&#xff0c;这里的“语言”是指使用规定格式和语法的代码。 2.结构图 3.角色 AbstractExpression&#xff08;抽象表达式&#xff09;&#xff1a;在抽象表达…...

[23年蓝桥杯] 买二赠一

题目描述 【问题描述】 某商场有 N 件商品&#xff0c;其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二 赠一” 的优惠活动&#xff0c;具体规则是&#xff1a; 每购买 2 件商品&#xff0c;假设其中较便宜的价格是 P &#xff08;如果两件商品价格一样&#xff0c; 则…...

PgSQL的with as语法

returning 返回的这一些字段&#xff0c;然后进行汇总为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&#xff08;&#xff09; 保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面 uni.redirectTo&#xff08;&#xff09; 关闭当前页面&#xff0c;跳转到应用内的某个页面。 uni.reLaunch&…...

面试算法-154-搜索二维矩阵 II

题目 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,…...

Java中Stream流介绍

Java 8引入的Stream API是Java中处理集合的一种高效方式&#xff0c;它提供了一种高级的迭代方式&#xff0c;允许你以声明式方式处理数据。Stream API可以对数据执行复杂的查询操作&#xff0c;而不需要编写冗长且复杂的循环语句。下面是一些使用Stream API的常见场景和示例&a…...

深度学习的层、算子和函数空间

目录 一、层、算子和函数空间概念 二、层&#xff08;Layers&#xff09; 三、算子&#xff08;Operators&#xff09; 3.1常见算子 3.2常见算子的性质 四、函数空间&#xff08;Function Space&#xff09; 一、层、算子和函数空间概念 层&#xff08;Layers&#xff09…...

Pillow教程11:九宫格切图的实现方法(安排!!!)

---------------Pillow教程集合--------------- Python项目18&#xff1a;使用Pillow模块&#xff0c;随机生成4位数的图片验证码 Python教程93&#xff1a;初识Pillow模块&#xff08;创建Image对象查看属性图片的保存与缩放&#xff09; Pillow教程02&#xff1a;图片的裁…...

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安装软件 安装&#xff1a; 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】单例模式

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

Linux|从 STDIN 读取 Awk 输入

简介 在之前关于 Awk 工具的系列文章中&#xff0c;主要探讨了如何从文件中读取数据。但如果你希望从标准输入&#xff08;STDIN&#xff09;中读取数据&#xff0c;又该如何操作呢&#xff1f; 在本文中&#xff0c;将介绍几个示例&#xff0c;展示如何使用 Awk 来过滤其他命令…...

关于K8S集群中maste节点r和worker节点的20道面试题

1. 什么是Kubernetes&#xff08;K8S&#xff09;&#xff1f; Kubernetes&#xff08;通常简称为K8S&#xff09;是一种开源的容器编排平台&#xff0c;用于自动化部署、扩展和管理容器化应用程序。以下是Kubernetes的一些核心特性和优势&#xff1a; 自动化部署和扩展&…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...