C++二分算法:1713得到子序列的最少操作次数

米饭5个月前行业资讯589

本文涉及的基础知识点

二分查找算法合集


LeetCode1713题目

给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。

每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。

请你返回 最少 操作次数,使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素(可能一个元素都不删除),同时不改变其余元素的相对顺序得到的数组。比方说,[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列(加粗元素),但 [2,4,2] 不是子序列。

示例 1:

输入:target = [5,1,3], arr = [9,4,2,3,4]

输出:2

解释:你可以添加 5 和 1 ,使得 arr 变为 [5,9,4,1,2,3,4] ,target 为 arr 的子序列。

示例 2:

输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]

输出:3

参数范围:

1 <= target.length, arr.length <= 105

1 <= target[i], arr[i] <= 109

target 不包含任何重复元素。


分析

时间复杂度

O(nlogn),枚举arr的时间复杂度O(n),处理arr的每个元素都需要二分查找,时间复杂度O(n)。


最长公共子序列

本题转换一下就是:求 target的长度减两者的公共最长子序列的长度。


注意

target 中没有重复的元素,所以可以将nums[i]替换成它的索引。比如: target= {3,2,1},arr={2,3}。

替换成{0,1,2},{1,0}。arr存在,但target中不存在的元素,忽略掉,比如:设置为-1,处理的时候忽略掉。


大致步骤。

一,值变索引。

 mValueIndex[target[i]] = i;

二,依次枚举arr[i]。

for (const auto& n : arr)


vLenToEndIndex

vLenToEndIndex见的淘汰

vLenToEndIndex[i]如果有多个值,淘汰值大的。因为索引越小越容易组成新的子序列。


含义

vLenToEndIndex[i]为j,表示目前长度为i+1的子序列的末尾元素的值(同时也是target中的索引)是j。

构建以n结果的公共子序列的两者方法:




只有n一个元素的子序列
如果存在j<n,且以j结尾的公共序列此系列+i


令n在 arr中的索引为i,则除掉被淘汰的公共子序列,以arr[0,i)结尾的公共子序列都在vLenToEndIndex中。vLenToEndIndex[j]小于n,说明vLenToEndIndex[j]在target的位置在n之前。也就是此子系列的结尾元素在target和arr中,都在n之前,故可以组成新的子序列。如果有多个vLenToEndIndex[j]符合条件取最大j。j+1就是新系列的长度。


vLenToEndIndex是严格递增

一,初始状态下,空向量符合严格递增。

二,如果vLenToEndIndex所有元素小于n,则n追加到最后,显然是严格递增。

三,it是第一个大于等于n的数。也就是a,it之前的数都小于n。b,由于vLenToEndIndex是严格递增,所有it后面的数大于it,而it>=n,故后面的元素>n。所以以下代码不会影响严格递增。

*it = n;

代码

核心代码

class Solution {

public:

int minOperations(vector& target, vector& arr) {

unordered_map<int, int> mValueIndex;

for (int i = 0; i < target.size(); i++)

{

mValueIndex[target[i]] = i;

}

for (auto& n : arr)

{

if (mValueIndex.count(n))

{

n = mValueIndex[n];

}

else

{

n = -1;

}

}

vector vLenToEndIndex;

for (const auto& n : arr)

{

if (-1 == n)

{

continue;

}

auto it = std::lower_bound(vLenToEndIndex.begin(), vLenToEndIndex.end(), n);

if (vLenToEndIndex.end() == it)

{

vLenToEndIndex.emplace_back(n);

}

else

{

if (n < *it)

{

*it = n;

}

}

}

return target.size() - vLenToEndIndex.size();

}

};


优化后的代码

直接将符合的arr[i]复制到新数组中。

class Solution {
public:
	int minOperations(vector<int>& target, const vector<int>& arr) {
		unordered_map<int, int> mValueIndex;
		for (int i = 0; i < target.size(); i++)
		{
			mValueIndex[target[i]] = i;
		}
		vector<int> vNew;
		for (auto& n : arr)
		{
			if (mValueIndex.count(n))
			{
				vNew.emplace_back(mValueIndex[n]);
			}
		}
		vector<int> vLenToEndIndex;
		for (const auto& n : vNew)
		{
			auto it = std::lower_bound(vLenToEndIndex.begin(), vLenToEndIndex.end(), n);
			if (vLenToEndIndex.end() == it)
			{
				vLenToEndIndex.emplace_back(n);
			}
			else
			{
				if (n < *it)
				{
					*it = n;
				}
			}
		}
		return target.size() - vLenToEndIndex.size();
	}
};

测试用例

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 target, arr;

int res;
{
	Solution slu;
	target = { 5, 1, 3 }, arr = { 9, 4, 2, 3, 4 };
	res = slu.minOperations(target, arr);
	Assert(2, res);
}
{
	Solution slu;
	target = { 6,4,8,1,3,2 }, arr = { 4,7,6,2,3,8,6,1 };
	res = slu.minOperations(target, arr);
	Assert(3, res);
}

//CConsole::Out(res);

}


2023年3月旧版

class Solution {

public:

int minOperations(vector& target, vector& arr) {

std::unordered_map<int, int> mValueToIndex;

for (int i = 0; i < target.size(); i++)

{

mValueToIndex[target[i]] = i+1;

}

for (const auto& a : arr)

{

if (mValueToIndex.count(a))

{

m_arr.push_back(mValueToIndex[a]);

}

}

Do();

return target.size() - m_iMaxPublicNum;

}

void Do()

{

std::map<int, int> mValueNum;

for (const auto& a : m_arr)

{

auto it = mValueNum.lower_bound(a);

int iNum = 1;

if (mValueNum.begin() != it)

{

auto tmp = it;

iNum = (–tmp)->second + 1;

}

if (mValueNum.end() != it)

{

if (iNum >= it->second)

{

mValueNum.erase(it);

}

}

m_iMaxPublicNum = max(m_iMaxPublicNum, iNum);

mValueNum[a] = iNum;

}

}

vector m_arr;

int m_iMaxPublicNum=0;//最大公共系列

};



本文系转载,版权归原作者所有,如若侵权请联系我们进行删除!  

云掣基于多年在运维领域的丰富时间经验,编写了《云运维服务白皮书》,欢迎大家互相交流学习:

《云运维服务白皮书》下载地址:https://fs80.cn/v2kbbq

想了解更多大数据运维托管服务、数据库运维托管服务、应用系统运维托管服务的的客户,欢迎点击云掣官网沟通咨询:https://yunche.pro/?t=shequ


相关文章

Docker:技术架构的演进之路

Docker:技术架构的演进之路

前言技术架构是指在软件开发和系统构建中,为了满足业务需求和技术要求,对系统的整体结构、组件、接口、数据流以及技术选型等方面进行的详细设计和规划。它是软件开发过程中的重要组成部分,为开发团队提供了明确的...

Linux CentOS7虚拟机配置静态IP并允许上网的配置方法

Linux CentOS7虚拟机配置静态IP并允许上网的配置方法

前言当我们成功的将CentOS镜像安装到了我们的虚拟机上后,可是这个时候,虚拟机还没有配置IP信息,为了后面开发方便,我们需要设置一个静态IP。一、开启本地电脑VMnet8本地电脑,右键点击网络-&g...

MyBatisPlus从零到一:快速入门与核心功能详解(2)

MyBatisPlus从零到一:快速入门与核心功能详解(2)

二、核心功能刚才的案例中都是以 id 为条件的简单 CRUD,一些复杂条件的 SQL 语句就要用到一些更高级的功能了。2.1 条件构造器:除了新增以外,修改、删除、查询的 SQL 语句都需要指定 wh...

Docker 基础与实战指南(2)

Docker 基础与实战指南(2)

二、Docker 基础接下来,我们一起来学习 Docker 使用的一些基础知识,为将来部署项目打下基础。具体用法可以参考 Docker 官方文档:https://docs.docker.com/2.1...

【计算机网络】详解数据链路层数据帧&Mac地址&ARP协议

【计算机网络】详解数据链路层数据帧&Mac地址&ARP协议

一、以太网帧         "以太网" 不是一种具体的网络,而是一种技术标准;既包含了数据链路层的内容,也包含了一些物理层的内容...

一文帮你理解整个SRE运维体系

一文帮你理解整个SRE运维体系

SRE运维体系的构建和工作职责划分。SRE工程师近年来的岗位需求逐年增加,被称为IT行业十大最受欢迎的行业之一。可观测性系统在任何有一定规模的企业内部,一旦推行起来整个SRE的运维模式,那么对于可观测...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。