C++二分算法:使数组严格递增

涉及知识点

动态规划 二分查找

题目

给你两个整数数组 arr1 和 arr2,返回使 arr1 严格递增所需要的最小「操作」数(可能为 0)。
每一步「操作」中,你可以分别从 arr1 和 arr2 中各选出一个索引,分别为 i 和 j,0 <= i < arr1.length 和 0 <= j < arr2.length,然后进行赋值运算 arr1[i] = arr2[j]。
如果无法让 arr1 严格递增,请返回 -1。
示例 1:
输入:arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出:1
解释:用 2 来替换 5,之后 arr1 = [1, 2, 3, 6, 7]。
示例 2:
输入:arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出:2
解释:用 3 来替换 5,然后用 4 来替换 3,得到 arr1 = [1, 3, 4, 6, 7]。
示例 3:
输入:arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出:-1
解释:无法使 arr1 严格递增。
*参数范围
1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

分析

时间复杂度

O(nnlogn)。两层循环,第一层枚举结尾O(n),第二层枚举前值O(n),寻找第一个大于nums[i]的值O(logn)。

注意

arr2中的值可以重复取,所以arr2中重复的值可以删除。直接用有序集合记录就可以了。dp和pre的key都是记录前值,value记录操作次数。如果preValue0<=preValue1且iNum0<=iNum1,那preValue1被淘汰。能选择preValue1则一定能选择preValue0,而iNum0更小。淘汰后,dp和pre的key是升序,value是降序。

处理思路

对于每个前值(前一个元素的值),有两种操作方式:

如果前者<当前值不替换
setHas中存在大于前值的数用符合条件的最小值替换

代码

核心代码

class Solution {
public:
	int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
		std::set<int> setHas(arr2.begin(), arr2.end());
		auto Add = [](map<int, int>&dp,int iValue, int iNum)
		{
			//如果iValue和iNum都大,则被淘汰。淘汰后,iVaule升序,iNum降序
			auto it = dp.upper_bound(iValue);
			if ((dp.begin() != it) && (std::prev(it)->second <= iNum))
			{
				return;//被淘汰
			}
			auto ij = it;
			for (; (dp.end() != ij) && (ij->second >= iNum); ++ij);
			dp.erase(it, ij);
			dp[iValue] = iNum;
		};
		map<int, int> pre;
		Add(pre, arr1.front(), 0);
		Add(pre, *setHas.begin(), 1);
		for (int i = 1; i < arr1.size(); i++)
		{
			map<int, int> dp;			
			for (const auto& [preValue, iNum] : pre)
			{
				if (preValue < arr1[i])
				{
					//不换
					Add(dp,arr1[i], iNum);
				}
				auto it = setHas.upper_bound(preValue);
				if (setHas.end()!= it )
				{
					//换
					Add(dp,*it, iNum + 1);
				}
			}
			dp.swap(pre);
		}
		return pre.empty() ? -1 : pre.rbegin()->second;
	}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vector arr1, arr2;
int res;
{
Solution slu;
arr1 = { 1, 5, 3, 6, 7 }, arr2 = { 1, 3, 2, 4 };
res = slu.makeArrayIncreasing(arr1, arr2);
Assert(1, res);
}
{
Solution slu;
arr1 = { 1,5,3,6,7 }, arr2 = { 4,3,1 };
res = slu.makeArrayIncreasing(arr1, arr2);
Assert(2, res);
}
{
Solution slu;
arr1 = { 1,5,3,6,7 }, arr2 = { 1,6,3,3 };
res = slu.makeArrayIncreasing(arr1, arr2);
Assert(-1, res);
}
{
Solution slu;
arr1 = { 19, 18, 7, 4, 11, 8, 3, 10, 5, 8, 13 }, arr2 = { 13, 16, 9, 14, 3, 12, 15, 4, 21, 18, 1, 8, 17, 0, 3, 18 };
res = slu.makeArrayIncreasing(arr1, arr2);
Assert(9, res);
}

//CConsole::Out(res);

}

优化

Add(pre, -1, 0);
		for (int i = 0; i < arr1.size(); i++)
		

可以修改初始状态:
前值比任何数都小,操作次数0。从0开始循环。

2023年1月旧版

class Solution {
public:
int makeArrayIncreasing(vector& arr1, vector& arr2) {
std::set set2;
std::copy(arr2.begin(), arr2.end(), std::inserter(set2, set2.begin()));
std::vector canSel;
std::copy(set2.begin(), set2.end(), std::back_inserter(canSel));
std::unordered_map<int, int> mValueIndex;
for (int i = 0; i + 1 < canSel.size(); i++)
{
mValueIndex[canSel[i]] = i + 1;
}
for (int i = 0 ; i < arr1.size(); i++)
{
int index = std::upper_bound(canSel.begin(), canSel.end(), arr1[i]) - canSel.begin();
if (index < canSel.size())
{
mValueIndex[arr1[i]] = index;
}
}
mValueIndex[-1] = 0;
vector pre(arr1.size() + 1, INT_MAX);
pre[0] = -1;//操作0次后,可以选择canSel[0];
for (int index1 = 0; index1 < arr1.size(); index1++)
{
const auto& data = arr1[index1];
std::vector dp(arr1.size() + 1, INT_MAX);
for (int i = 0; i < pre.size(); i++)
{
const int iValue = pre[i];
if (INT_MAX == iValue)
{
continue;
}
if (mValueIndex.count(iValue))
{
const int iNewValue = canSel[mValueIndex[iValue]];
dp[i + 1] = min(dp[i + 1], iNewValue);
}
if (data > iValue)
{
dp[i] = min(dp[i], data);
}
}
pre.swap(dp);
}
for (int i = 0; i < pre.size(); i++)
{
if (INT_MAX != pre[i])
{
return i;
}
}
return -1;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

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

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

相关文章

OceanBase:中国场景推动树立分布式数据库四项新标准

11月16日&#xff0c;在OceanBase2023年度发布会上&#xff0c;OceanBase CEO杨冰介绍&#xff0c;中国数字经济的蓬勃发展催生了对分布式数据库的强大需求&#xff0c;这种需求也牵引了OceanBase坚定投入自主研发&#xff0c;从而推动树立了分布式数据库的四项新标准。 据了解…

【计算机组成原理】定点加法、减法运算

系列文章目录 绘制出纯整数(1字节)和纯小数的数轴 将十进制数20.59375&#xff0c;转换成754标准的32位浮点数的二进制存储格式 用双符号位补码求 x 0.1010011, y -0.1001010, 分别求出 x y, x - y&#xff0c;并判溢出

单例模式(常用)

单例模式&#xff08;单例设计模式) 在有些系统中&#xff0c;为了节省内存资源、保证数据内容的一致性&#xff0c;对某些类要求只能创建一个实例&#xff0c;这就是所谓的单例模式。 单例模式的定义与特点 单例&#xff08;Singleton&#xff09;模式的定义&#xff1a;指…

Maven项目指定main方法配置

例如有个maven工程 打包后 xxx.jar 而这个maven工程里可能有很多main方法,比如测试的main方法 插件指定 <build><plugins><plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-jar-plugin</artifactId>&…

KVM网络环境下vlan和trunk的理解

vmware exsi 平台&#xff0c;虚拟交换机管理界面的上行链路是什么意思 VMware ESXi中的虚拟交换机管理界面中的“上行链路”&#xff08;uplinks&#xff09;是指虚拟交换机连接到物理网络的物理网络适配器。在ESXi中&#xff0c;虚拟交换机&#xff08;vSwitch&#xff09;用…

【人工智能】本地运行开源项目MMSegmentation引发的问题

文章目录 ❌AssertionError: Torch not compiled with CUDA enabled问题描述问题分析解决方案总结参考文献 ❌AssertionError: Torch not compiled with CUDA enabled 问题描述 python demo/image_demo.py demo/demo.png configs/pspnet/pspnet_r50-d8_4xb2-40k_cityscapes-5…

rocketmq 安装dashboard1.0.0 mq消息控制台安装 rocketmq控制台安装 rocketmq-dashboard-1.0.0编译安装

1. 官网&#xff1a; 下载 | RocketMQ 2. dashboard安装包位置&#xff1a; 在连接最下面&#xff0c;点击download.zip即可 3. 需要安装maven, 编译命令&#xff1a; mvn clean install -U -Dmaven.test.skiptrue4. 启动jar: java -jar rocketmq-dashboard-1.0.0.jar &…

交换排序详讲:冒泡排序+快速排序(多方法+思路+图解+代码)

文章目录 交换排序一.冒泡排序二.快速排序1.挖坑法2.Hoare法 交换排序 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置将键值较大的记录向序列的尾部移动&#xff0c;键值较小的记录向序列的前部移动。 一.冒泡排序 /*** 冒泡排序* 时间复杂度 n^2* 空间复杂…

【开源】基于JAVA的大学兼职教师管理系统

项目编号&#xff1a; S 004 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S004&#xff0c;文末获取源码。} 项目编号&#xff1a;S004&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容三、界面展示3.1 登录注册3.2 学生教师管…

《effective C++》条款10

令operator返回一个reference to *this int main() {int a, b, c 5;a b c;cout << a; } 这个代码&#xff0c;很明显输出的是5。所以我们在写这种连续赋值的时候&#xff0c;其对应的赋值运算符应当返回一个*this &#xff1a; class A { public:A(string ss, int x) …

vs2017打开工程提示若要解决此问题,请使用以下选择启动 Visual Studio 安装程序: 用于 x86 和 x64 的 Visual C++ MFC

下载 error MSB8036: 找不到 Windows SDK 版本8.1。请安装所需的版本的 Windows SDK 或者在项目属性页中或通过右键单击解决方案并选择“重定解决方案目标”来更改 SDK 版本。 error&#xff1a;D8016 “/ZI”和“/Gy-”命令行选项不兼容 ”问题解决

linux systemd start stop enable disable命令区别

一、systemd 的服务在三个文件件下 /lib/systemd/system /etc/systemd/system /usr/lib/systemd/system 终于明白这几个命令的区别 systemd star systemd stop systemd enable systemd disable 二、 1、用ssh服务为例&#xff0c;&#xff0c;ssh是客户端&#xff0c;远程ss…

delphi电子处方流转(医院)

【delphi电子处方流转(医院)】支持 就诊登记、电子处方上传预核验、处方处方医保电子签名、电子处方上传、电子处方撤销、电子处方信息查询、电子处方审核结果查询、电子处方取药结果查询、电子处方药品目录查询等功能。

短视频账号矩阵系统源码

短视频账号矩阵系统源码搭建步骤包括以下几个方面&#xff1a; 1. 确定账号类型和目标受众&#xff1a;确定要运营的短视频账号类型&#xff0c;如搞笑、美食、美妆等&#xff0c;并明确目标受众和定位。 2. 准备账号资料&#xff1a;准备相关资质和资料&#xff0c;如营业执照…

数据结构--栈与队列

目录 前言 1.栈 1.1栈的概念及结构 1.2接口函数 1.3函数实现 1.4如何使用 2.队列 2.1队列的概念及结构 2.2接口函数 2.3函数实现 2.4如何使用 前言 前面我们已经学习了顺序表和链表&#xff0c;今天我们来学习栈与队列&#xff0c;这两种结构也属于线性表&#xff0c;实…

解决windeployqt打包exe的“VCINSTALLDIR is not set“问题

今天在使用windeployqt部署qt的.exe文件时&#xff0c; 出现如下错误&#xff1a; windeployqt HelloQt.exe图(1) 报"VCINSTALLDIR路径"找不到 出现这种情况的原因是&#xff1a;VCINSTALLDIR环境没有配置&#xff0c;需要把Visual Studio的编译路径: ## 1) 社区版…

2018年五一杯数学建模A题徐州潘安湖风景区游览路线设计解题全过程文档及程序

2019年五一杯数学建模 A题 徐州潘安湖风景区游览路线设计 原题再现 徐州是一个老工业基地和资源型城市&#xff0c;煤炭开采历史长达130年。长期煤炭开采在徐州累计形成采煤塌陷区达数十万亩。位于徐州市贾汪区西南部、紧邻马庄的潘安湖湿地公园原来就是徐州最大的、塌陷最严…

关系代数、SQL语句和Go语言示例

近些年&#xff0c;数据库领域发展日新月异&#xff0c;除传统的关系型数据库外&#xff0c;还出现了许多新型的数据库&#xff0c;比如&#xff1a;以HBase、Cassandra、MongoDB为代表的NoSQL数据库&#xff0c;以InfluxDB、TDEngine为代表的时序数据[1]库&#xff0c;以Neo4J…

【UE5】物体沿样条线移动

目录 效果 步骤 一、使用样条线创建路径 二、创建沿样条线路径移动的物体 三、定义可移动物体的生成器 效果 步骤 一、使用样条线创建路径 先创建一个Actor蓝图&#xff0c;这里命名为“BP_Line” 该蓝图中只需添加一个样条组件 将“BP_Line”拖入场景中 按住Alt鼠标左键…

生存分析后如何绘制亚组森林图?小白也能快速搞定!(附教程)

本周为大家重点介绍一下风暴统计平台的最新板块——亚组森林图&#xff01; 现在亚组分析好像越来越流行&#xff0c;无论是观察性研究还是RCT研究&#xff0c;亚组分析一般配备森林图。 比如这张图&#xff1a; 还有这个&#xff1a; 森林图不仅是画图的画法&#xff0c;背后还…