本文涉及的基礎知識點
二分查找算法合集
題目
給你一個數組 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
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。 |
| 子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
)
