LeetCode-2009. 使数组连续的最少操作数【数组 哈希表 二分查找 滑动窗口】

LeetCode-2009. 使数组连续的最少操作数【数组 哈希表 二分查找 滑动窗口】

  • 题目描述:
  • 解题思路一:正难则反+滑动窗口
  • 解题思路二:0
  • 解题思路三:0

题目描述:

给你一个整数数组 nums 。每一次操作中,你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件,那么它是 连续的 :

nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说,nums = [4, 2, 5, 3] 是 连续的 ,但是 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 <= nums.length <= 105
1 <= nums[i] <= 109

解题思路一:正难则反+滑动窗口

正难则反,考虑最多保留多少个元素不变。

由于元素的位置不影响答案,且要求所有元素互不相同,我们可以将 nums 从小到大排序,并去掉重复元素。

设 x 是连续数字的最大值,则连续数字的范围为闭区间 [x−n+1,x],其中 n 是 nums 的长度。

设 a 为 nums 排序去重后的数组。把 a[i]画在一条数轴上,本题相当于有一个长度为 n 的滑动窗口,我们需要计算窗口内最多可以包含多少个数轴上的点。

定理:只需要枚举 a[i] 作为窗口的右端点。

证明:在窗口从左向右滑动的过程中,如果窗口右端点处没有点,那么继续滑动,在滑到下一个点之前,窗口内包含的点的个数是不会增多的。
在这里插入图片描述
为了算出窗口内有多少个点,我们需要知道窗口包含的最左边的点在哪,设这个点的位置是 a[left],则它必须大于等于窗口的左边界,即

a[left]≥a[i]−n+1
此时窗口内有 i−left+1个点。

注意i - left + 1是nums数组中在滑动窗口中的个数

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        a = sorted(set(nums)) # 去重排序
        ans = left = 0
        for i, x in enumerate(a):
            while a[left] < x - n + 1: # a[left] 不在窗口内
                left += 1
            ans = max(ans, i - left + 1) # 统计最长的连续数组长度
        return n - ans

时间复杂度:O(nlogn)
空间复杂度:O(n) 哈希表

解题思路二:0


时间复杂度:O(n)
空间复杂度:O(n)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532695.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

rabbitmq延迟队列的使用

rabbitmq延迟队列的使用 1、场景&#xff1a; 1.定时发布文章 2.秒杀之后&#xff0c;给30分钟时间进行支付&#xff0c;如果30分钟后&#xff0c;没有支付&#xff0c;订单取消。 3.预约餐厅&#xff0c;提前半个小时发短信通知用户。 A -> 13:00 17:00 16:30 延迟时间&a…

麒麟V10安装Redis6.2.6

1、下载redis安装包 Redis各版本下载&#xff1a;https://download.redis.io/releases/ 2、将下载后的.tar.gz压缩包上传到到服务器自定义文件夹下 3、 解压文件 tar -zxvf redis-6.2.6.tar.gzmv redis-6.2.6 redis4、安装redis 在redis文件夹下输入make指令 cd /opt/redi…

性能测试 —— Jmeter 命令行详细

我们在启动Jmeter时 会看见&#xff1a;Don’t use GUI mode for load testing !, only for Test creation and Test debugging.For load testing, use CLI Mode (was NON GUI) 这句话的意思就是说&#xff0c;不要使用gui模式进行负载测试&#xff0c;gui模式仅仅是创建脚本…

【LeetCode: 628. 三个数的最大乘积 + 排序 + 贪心】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

C++ linked_hash_map按顺序保存的容器

HashMap中不存在保存顺序的机制。而在LinkedHashMap中可以保持两种顺序&#xff0c;分别是插入顺序和访问顺序&#xff0c;这个是可以在LinkedHashMap的初始化方法中进行指定的。相对于访问顺序&#xff0c;按照插入顺序进行编排被使用到的场景更多一些&#xff0c;所以默认是按…

实现鼠标在页面点击出现焦点及大十字星

近段时间&#xff0c;在完成项目进度情况显示时候&#xff0c;用户在操作鼠标时候&#xff0c;显示当鼠标所在位置对应时间如下图所示 代码实现步骤如下&#xff1a; 1.首先引用 jquery.1.7.js 2.再次引用raphael.js 3.然后引用graphics.js 4.最后引用mfocus.js 其中mfocu…

【leetcode面试经典150题】38. 生命游戏(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

蓝桥杯第九届省赛真题代码——彩灯控制器-附详细讲解思路

1. 比赛题目要求 2. 功能实现推荐步骤 首先&#xff0c;添加头文件&#xff0c;搭建最底层的代码&#xff0c;实现基本的流水灯运转与数码管显示rb2的电阻值 然后&#xff0c;进行pwm脉宽调制&#xff0c;实现rb2数值不同&#xff0c;从而灯光亮度不同。并作出数码管的多窗口…

Java GC了解

Jstack找到线程的快照 jvm提供其他命令作用 jps&#xff1a; 虚拟机进程状况工具&#xff0c;类似linux的ps命令 jstat&#xff1a;虚拟机统计信息监视工具&#xff0c;经常看gc情况的会使用到 jinfo: java配置信息工具 jmap&#xff1a; java内存映射工具&#xff0c;dump&am…

别催了!超真实格行5G随身WiFi问答它来了!格行5G随身WiFi靠谱吗? 看完这篇文章你就懂了?

总让我测格行5G随身WiFi&#xff0c;一直催催催。这下别催了&#xff0c;你们要的格行5G随身WiFi真实测评它来了&#xff01;这次着重回答大家最关心&#xff0c;问的最多的几个问题&#xff01; 一、问&#xff1a;格行5G随身WiFi网速怎么样&#xff1f; 答&#xff1a;格行5G…

网络编程套接字(一)

目录 一、源IP和目的IP 二、端口号 三、UDP协议和TCP协议 四、网络字节序 五、socket编程 1、socket 常见接口 2、struct sockaddr结构体 一、源IP和目的IP IP地址是IP协议提供的一种统一的地址格式&#xff0c;它为互联网上的每一个网络和每一台主机分配一个逻辑地址&am…

原子操作和竞争条件

所有系统调用都是以原子操作方式执行的。之所以这么说&#xff0c;是指内核保证了某系统调用中的所有步骤会作为独立操作而一次性加以执行&#xff0c;其间不会为其他进程或线程所中断。原子性是某些操作得以圆满成功的关键所在。特别是它规避了竞争状态&#xff08;race condi…

解决ModuleNotFoundError: No module named ‘exceptions‘

一、问题描述 使用python语言处理docx文档&#xff0c;在安装docx库时出现问题&#xff0c;No module named ‘exceptions‘ 二、解决方法 卸载docx&#xff0c;安装python-docx。 pip uninstall docx pip install python-docx 问题解决&#xff01;

SSRF靶场

SSRF概述 ​ 强制服务器发送一个攻击者的请求 ​ 互联网上的很多web应用提供了从其他服务器&#xff08;也可以是本地)获取数据的功能。使用用户指定的URL&#xff0c;web应用可以获取图片&#xff08;载入图片&#xff09;、文件资源&#xff08;下载或读取)。如下图所示&…

[lesson17]对象的构造(上)

对象的构造(上) 对象的初始化 从程序设计的角度&#xff0c;对象只是变量&#xff0c;因此&#xff1a; 在栈上常见对象时&#xff0c;成员变量初始为随机值在堆上创建对象时&#xff0c;成员变量初始为随机值在静态存储区创建对象时&#xff0c;成员变量初始为0值 生活中的对…

算法打卡day41|动态规划篇09| Leetcode198.打家劫舍、213.打家劫舍II、337.打家劫舍 III

算法题 Leetcode 198.打家劫舍 题目链接:198.打家劫舍 大佬视频讲解&#xff1a;198.打家劫舍视频讲解 个人思路 偷还是偷&#xff0c;这取决于前一个和前两个房是否被偷了&#xff0c;这种存在依赖关系的题目可以用动态规划解决。 解法 动态规划 动规五部曲&#xff1a;…

生鲜蔬果配送小程序开发攻略

随着互联网的快速发展&#xff0c;电商行业也在不断壮大。生鲜蔬果作为日常生活必需品&#xff0c;在线销售的需求也在不断增加。为了满足这一需求&#xff0c;开发一款生鲜蔬果配送小程序成为了必要的事情。下面就给大家介绍开发这款小程序的攻略。 1. 确定开发需求 首先&…

Java Swing游戏开发学习23

内容来自RyiSnow视频讲解 这一节讲的是Character Status角色状态或属性。 前言 这一节讲的是实现角色状态或属性的显示&#xff0c;就有点像RPG游戏中&#xff0c;人物属性显示的面板&#xff0c;其中有玩家的装备、玩家的等级&#xff0c;各种防御值、闪避值、跑速什么的。…

基于BP神经网络的分类预测模型matlab代码

基于BP神经网络的分类预测模型matlab代码&#xff0c;该数据集下&#xff0c;本模型的表现优异&#xff0c;训练集准确率可达97%&#xff0c;测试集准确率可达93.5%&#xff0c;表现优异。注释十分齐全适合新手学习。 代码获取链接&#xff1a;基于BP神经网络的分类预测模型ma…

SpringBoot3 + uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作(最新)

SpringBoot3 uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作 最终效果图uniapp 的源码UpLoadFile.vuedeleteOssFile.jshttp.js SpringBoot3 的源码FileUploadController.javaAliOssUtil.java 最终效果图 uniapp 的源码 UpLoadFile.vue <tem…