网站开发硬件工程师待遇,微信商城有哪些第三方平台,网站流量成本,专业做网站公司排名本文涉及的基础知识点
二分查找算法合集
题目
给你一个数组 target #xff0c;包含若干 互不相同 的整数#xff0c;以及另一个整数数组 arr #xff0c;arr 可能 包含重复元素。 每一次操作中#xff0c;你可以在 arr 的任意位置插入任一整数。比方说#xff0c;如果…本文涉及的基础知识点
二分查找算法合集
题目
给你一个数组 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表示目前长度为i1的子序列的末尾元素的值同时也是target中的索引)是j。 构建以n结果的公共子序列的两者方法
只有n一个元素的子序列如果存在jn且以j结尾的公共序列此系列i
令n在 arr中的索引为i则除掉被淘汰的公共子序列以arr[0,i)结尾的公共子序列都在vLenToEndIndex中。vLenToEndIndex[j]小于n说明vLenToEndIndex[j]在target的位置在n之前。也就是此子系列的结尾元素在target和arr中都在n之前故可以组成新的子序列。如果有多个vLenToEndIndex[j]符合条件取最大j。j1就是新系列的长度。
vLenToEndIndex是严格递增
一初始状态下空向量符合严格递增。 二如果vLenToEndIndex所有元素小于n则n追加到最后显然是严格递增。 三it是第一个大于等于n的数。也就是a,it之前的数都小于n。b,由于vLenToEndIndex是严格递增所有it后面的数大于it而itn故后面的元素n。所以以下代码不会影响严格递增。
*it n;代码
核心代码
class Solution { public: int minOperations(vector target, vector arr) { unordered_mapint, 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(vectorint target, const vectorint arr) {unordered_mapint, int mValueIndex;for (int i 0; i target.size(); i){mValueIndex[target[i]] i;}vectorint vNew;for (auto n : arr){if (mValueIndex.count(n)){vNew.emplace_back(mValueIndex[n]);}}vectorint 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_mapint, int mValueToIndex; for (int i 0; i target.size(); i) { mValueToIndex[target[i]] i1; } for (const auto a : arr) { if (mValueToIndex.count(a)) { m_arr.push_back(mValueToIndex[a]); } } Do(); return target.size() - m_iMaxPublicNum; } void Do() { std::mapint, 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_iMaxPublicNum0;//最大公共系列 };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
