题目描述
给定一个数组 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]
不是子序列。
样例
输入:target = [5,1,3], arr = [9,4,2,3,4]
输出:2
解释:你可以添加 5 和 1,使得 arr 变为 [5,9,4,1,2,3,4],target 为 arr 的子序列。
输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出:3
限制
1 <= target.length, arr.length <= 10^5
1 <= target[i], arr[i] <= 10^9
target
不包含任何重复元素。
算法
(贪心,动态规划,树状数组) $O(n \log n)$
- 由于
target
不含有重复数字,故其本身可以当做一种排列。 - 将
target(i)
映射到i + 1
,然后在arr
上,对着映射关系求出最长上升子序列。因为插入一个数字的代价为 1,所以直接寻找最长上升子序列就是全局最优。 - $n$ 减去最长上升子序列的长度就是答案。
时间复杂度
- 构造哈希表的时间复杂度为 $O(n)$。
- 用树状数组优化的最长上升子序列的时间复杂度为 $O(n \log n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表和树状数组。
C++ 代码
#define max(x, y) ((x) > (y) ? (x) : (y))
class Solution {
private:
vector<int> f;
void update(int x, int y, int n) {
for (; x <= n; x += x & -x)
f[x] = max(f[x], y);
}
int query(int x) {
int ma = 0;
for (; x; x -= x & -x)
ma = max(ma, f[x]);
return ma;
}
public:
int minOperations(vector<int>& target, vector<int>& arr) {
const int n = target.size();
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[target[i]] = i + 1;
f.resize(n + 1, 0);
const int m = arr.size();
int res = 0;
for (int i = 0; i < m; i++) {
if (mp.find(arr[i]) == mp.end())
continue;
int x = mp[arr[i]];
int t = query(x - 1) + 1;
update(x, t, n);
if (t > res)
res = t;
}
return n - res;
}
};
树状数组有优化好像和y总讲的那个存储单调结尾的方法不一样,学到了