Leetcode - 2009. 使数组连续的最少操作数

文章目录

  • 解析
  • 排序 + 原地去重 + 滑动窗口
  • AC CODE



题目链接:Leetcode - 2009. 使数组连续的最少操作数

在这里插入图片描述


解析

题中所述的连续数组就是一串连续的自然数,想问需要多少次操作能将原数组变为连续的数。
我们排序去重,用逆向思维想能保留的数字数目最多是多少,及用滑动窗口来获取最大数目。


排序 + 原地去重 + 滑动窗口

排序:快速排序。
原地去重:可参考 26. 删除有序数组中的重复项
滑动窗口:以序号i枚举窗口的右边界,也就是让数组中的每一个数都充当一次右边界,然后我们的左边界从0开始,看是否符合窗口大小,不符合就一直推进左边界到合法,然后重新计算窗口内的数字多少,取最大值,此值就是我们能保留的数目的最大值,那么需要修改的最小数目用数组长度减去保留的最多数目。


AC CODE

void quick_sort(int *q, int l, int r){if(l >= r) return;int i = l - 1, j = r + 1, x = q[(l + r) >> 1];while(i < j){do i++; while(q[i] < x);do j--; while(q[j] > x);if(i < j){int k = q[i];q[i] = q[j];q[j] = k;}}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}int dis(int *nums, int numsSize){int j = 0;for(int i = 0; i < numsSize; ++i){if(nums[j] != nums[i])nums[++j] = nums[i];}return j + 1;
}int minOperations(int* nums, int numsSize) {quick_sort(nums, 0, numsSize - 1);int m = dis(nums, numsSize), n = numsSize;int left = 0, ans = 0;for(int i = 0; i < m; ++i){while(nums[i] - n + 1 > nums[left])   left++;ans = fmax(ans, i - left + 1);}return n - ans;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

红外疼痛医学分会成立大会暨首届学术交流会即将盛大开幕

2024年4月7日&#xff0c;中国中医药研究促进会官网发布“关于召开红外疼痛医学分会成立大会暨首届学术交流会的第三轮通知”通知&#xff0c;大会开幕在即&#xff0c;这充分显示了官方对此次活动的高度重视。 本次大会将于 2024年4月19日至21日在重庆海兰云天海琴酒店隆重举行…

QT 使用redis ,连接并使用

一.redis安装 链接&#xff1a;https://pan.baidu.com/s/17fXKOj5M4VIypR0y5_xtHw 提取码&#xff1a;1234 1.下载得到文件夹如图 course_redis为安装包。 2.启动Redis服务 把安装包解压到某个路径下即可。 打开cmd窗口&#xff0c;切换到Redis安装路径&#xff0c;输入 r…

从人机界面设计黄金三法则视角看 ChatGPT 的界面设计的“好”与“坏”

热门文章推荐&#xff1a; &#xff08;1&#xff09;《为什么很多人工作 3 年 却只有 1 年经验&#xff1f;》&#xff08;2&#xff09;《一文掌握大模型提示词技巧&#xff1a;从战略到战术巧》&#xff08;3&#xff09;《AI 时代&#xff0c;程序员的出路在何方&#xff1…

Jenkins 安装部署

1、安装下载 官网地址&#xff1a;Jenkins 下载 war 包 1、前置环境 JDK 环境&#xff08;根据 Jenkins 版本不同&#xff0c;需要的 JDK 版本不同&#xff0c;目前需要 JDK11 的版本来支持&#xff09;Maven maven 官网下载压缩包 &#xff0c;并将其传输到服务器&#xf…

模拟多模态大模型gradio使用教程

文章目录 前言一、使用change监听demo1、代码3、网页结果显示4、输入信息结果显示 二、Button功能的demo1、代码2、结果显示3、变换参数结果显示 三、参数gr.Slider滑动demo1、代码2、结果显示3、具有下拉参数代码4、具有下拉结果显示 四、模拟多模态大模型网页demo1、代码2、界…

【机器学习300问】59、计算图是如何帮助人们理解反向传播的?

在学习神经网络的时候&#xff0c;势必会学到误差反向传播&#xff0c;它对于神经网络的意义极其重大&#xff0c;它是训练多层前馈神经网络的核心算法&#xff0c;也是机器学习和深度学习领域中最为重要的算法之一。要正确理解误差反向传播&#xff0c;不妨借助一个工具——计…

测开面经(pytest测试案例,接口断言,多并发断言)

pytest对用户登录接口进行自动化脚本设计 a. 创建一个名为"test_login.py"的测试文件&#xff0c;编写以下测试脚本 import pytest import requests# 测试用例1&#xff1a;验证登录成功的情况 # 第一个测试用例验证登录成功的情况&#xff0c;发送有效的用户名和密…

linux:du和df区别

文章目录 1. 概述2. du 命令2. df 命令3. 区别总结 1. 概述 du 和 df 都是 Linux 系统中用于查看磁盘空间使用情况的命令&#xff0c;但它们的功能和用法有所不同。 2. du 命令 du 是 “disk usage” 的缩写&#xff0c;用于显示文件或目录的磁盘使用情况。du 命令用于查看指…

Redis客户端

2.Redis客户端 安装完成Redis&#xff0c;我们就可以操作Redis&#xff0c;实现数据的CRUD了。这需要用到Redis客户端&#xff0c;包括&#xff1a; 命令行客户端图形化桌面客户端编程客户端 2.1.Redis命令行客户端 Redis安装完成后就自带了命令行客户端&#xff1a;redis-…

二分查找 -- 力扣(LeetCode)第704题

题目 https://leetcode.cn/problems/binary-search/description/ 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例…

计算机网络针对交换机的配置

实验 目的 交换机的基本配置&#xff0c;交换机VLAN配置 实验条件 Windows&#xff0c;Cisco packet tracer 实验 内容 交换机的基本配置&#xff0c;交换机VLAN配置 实验 过程 一、交换机的基本配置 进入特权模式 Switch>enable 进入配置模式 Switch#configure ter…

腾讯电商运营起来竟然这么简单!视频号小店操作玩法一文详解!

大家好&#xff0c;我是电商小布。 在新型电商玩法的兴起下&#xff0c;很多的平台都在电商行业内分到了一杯羹。 腾讯自然也就坐不住了&#xff0c;背靠自身的视频号平台&#xff0c;推出了视频号小店这个项目。 有很多的小伙伴想要趁着这个初期阶段&#xff0c;来加入到其…

数据结构与算法:哈希表

目录 1.哈希表和哈希 1.1.知识引入 1.2.为什么需要哈希表呢&#xff1f; 2.简易的哈希表 2.1.哈希表的基础结构 2.2.如何实现基础的哈希表 2.2.1.增 2.2.2.删 2.2.3.查 2.3.泛型编程下的哈希表 3.简易的哈希桶 1.哈希表和哈希 1.1.知识引入 哈希表&#xff08;Hash …

代码随想录-算法训练营day02【滑动窗口、螺旋矩阵】

专栏笔记&#xff1a;https://blog.csdn.net/weixin_44949135/category_10335122.html https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG?uc71ed002e4554fee8c262b2a4a4935d8977.有序数组的平方 &#xff0c;209.长度最小的子数组 &#xff0c;59.螺旋矩阵II &#xff0c;总结 建议…

【C++进阶】用哈希实现unordered_set和unordered_map的模拟

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 总有光环在陨落&#xff0c;总有新星在闪烁 前言&#xff1a; 之前我…

烧坏两块单片机,不知道原因?

没有看你的原理图&#xff0c;以下是造成烧毁芯片的几个环节&#xff1a; 1. 最大的可能性是你的单片机电机控制输出与电机驱动电路没有隔离。 我的经验&#xff0c;使用STM32控制电机&#xff0c;无论是直流电机脉宽调制&#xff0c;还是步进电机控制&#xff0c;控制电路与…

Ubuntu 20.04.06 PCL C++学习记录(十六)

[TOC]PCL中点云分割模块的学习 学习背景 参考书籍&#xff1a;《点云库PCL从入门到精通》以及官方代码PCL官方代码链接,&#xff0c;PCL版本为1.10.0&#xff0c;CMake版本为3.16 学习内容 用一组点云数据做简单的平面的分割 源代码及所用函数 源代码 #include<iostr…

机器学习笔记 - 深度学习遇到超大图像怎么办?使用 xT 对极大图像进行建模论文简读

作为计算机视觉研究人员,在处理大图像时,避免不了受到硬件的限制,毕竟大图像已经不再罕见,手机的相机和绕地球运行的卫星上的相机可以拍摄如此超大的照片,遇到超大图像的时候,我们当前最好的模型和硬件都会达到极限。 所以通常我们在处理大图像时会做出两个次优选择之一:…

【频繁模式挖掘】FP-Tree算法(附Python实现)

一、实验内容简介 该实验主要使用频繁模式和关联规则进行数据挖掘&#xff0c;在已经使用过Apriori算法挖掘频繁模式后&#xff0c;这次使用FP-tree算法来编写和设计程序&#xff0c;依然使用不同规模的数据集来检验效果&#xff0c;最后分析和探讨实验结果&#xff0c;看其是…

微服务架构下,如何通过弱依赖原则保障系统高可用?

前言 当我初次接触高可用这个概念的时候&#xff0c;对高可用的【少依赖原则】和【弱依赖原则】的边界感模糊&#xff0c;甚至有些“傻傻分不清楚”。这两个原则都关注降低模块之间的依赖关系&#xff0c;但它们之间的确存在某些差异。 那么&#xff0c;「少依赖原则」和「弱…