本文涉及的基础知识点
题目
给你一个数组 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;//最大公共系列 };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
