得到子序列的最少操作次数

发表于 更新于 分类于

    1713. 得到子序列的最少操作次数

    给你一个数组 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：

    ```txt

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

    输出：2

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

    ```

    示例 2：

    ```txt

    输入：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 不包含任何重复元素。

题目

1713. 得到子序列的最少操作次数

给你一个数组 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：

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

示例 2：

1
2
输入：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 不包含任何重复元素。

题解

方法一：

思路

惊喜一遍过。
一个类似最长上升子序列的问题

初步思路

求得arr中的一个子序列，该序列也是target中的一个子序列，只要让这个子序列尽可能的长，最后的答案便是用arr的长度减该子序列的长度。

设dp[i] 为arr前i个数中与target的最长公共子序列。

可遍历arr中元素，若当前遍历元素为num，则判断：

  • 若num不在target中，则dp[i] = dp[i-1]
  • 若num在target中，要求$dp[i]=之前遍历过的在target中的元素的最大dp值+1=dp[k]+1,k \in [0,i) \wedge k \in target$

时间复杂度是O(n^2)

可以采用最长上升子序列的O(nlogn)算法的优化方式。

优化

设dp[i] ，i是target与arr共同的子序列的长度，dp[i]是该长度下的子序列最后一个元素在target中的下标。dp[0]=-1，因为dp[]是升序的，保持升序可以方便用二分查找。

用哈希表map将每个target中的元素映射为各自对应的下标。
遍历arr数组，当前元素为num：

  • 当num不在map中时，说明该元素不会为增长公共子序列做出贡献。不做处理
  • 当num在map中时，则判断与dp[len]的大小，len是遍历到当前时最长公共子序列长度。
    • 若dp[len]<map[num], 在target中当前数字前有len个数字，则最长子序列增长。dp[++len] = map[num]
    • 若dp[len]>=map[num], 不能增长，但是可以某长度的子序列末元素下标，对于相同长度的子序列，最后元素的下标越靠前越好。这里可以采用二分查找，找到第一个大于等于当前map[num]的值然后替换。

最后的答案便是target的长度减去len。

时间复杂度$O(nlogn)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int dp[100005];//在arr找出一个子序列，该子序列也是target的子序列，长度为i，dp[i]是子序列的最后一个元素在target中的下标
    int minOperations(vector<int>& target, vector<int>& arr) {
        dp[0] = -1;//长度为0，在target中不存在
        int len = 0;
        unordered_map<int,int> mp;//将target的元素映射为它自己的下标
        for (int i=0; i<target.size(); i++) mp[target[i]] = i;
        for (int i=0; i<arr.size(); i++) {
            if (mp.count(arr[i])) {//若该值不属于target则len长度保持不变
                int cur = mp[arr[i]];
                if (cur>dp[len]) dp[++len] = mp[arr[i]];
                //dp[] 是升序的，二分查找找到顺序第一个大于等于当前然后替换它。
                //dp[len] >= mp[arr[i]], 二分查找区间[0,len)
                int l=0, r=len, m;
                while (l<r) {
                    m = l + (r-l)/2;
                    if (dp[m] >= cur) {
                        r = m;
                    } else {
                        l = m+1;
                    }
                }
                dp[r] = cur;
            }
        }
        return target.size()-len;
    }
};

方法二：

思路

可以用线段树求当前位置之前的最大递增子序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    #define ll long long
    #define N 100005
    struct Seg{
        int l, r;
        ll val;
    } seg[N<<2];

    void push_up(Seg& u, const Seg& l, const Seg& r) {
        u.val = max(l.val, r.val);
    }
    void seg_build(int id, int l, int r) {
        seg[id].l = l; seg[id].r = r;
        if (l == r) {
            seg[id].val = 0;
            // cin >> seg[id].val;
            return ;
        }
        int m = l+r>>1;
        seg_build(id<<1, l, m);
        seg_build(id<<1|1, m+1, r);
        push_up(seg[id], seg[id<<1], seg[id<<1|1]);
    }

    void seg_update(int id, int p, ll val) {
        if (p <= seg[id].l && seg[id].r <= p) {
            seg[id].val = max(seg[id].val, val);
            return ;
        }
        int m = seg[id].l + seg[id].r >> 1;
        if (p <= m) seg_update(id<<1, p, val);
        if (m < p) seg_update(id<<1|1, p, val);
        push_up(seg[id], seg[id<<1], seg[id<<1|1]);
    }

    ll seg_query(int id, int l, int r) {
        if (l <= seg[id].l && seg[id].r <= r) {
            return seg[id].val;
        }
        ll rt = 0;
        int m = seg[id].l + seg[id].r >> 1;
        if (l <= m) rt = max(rt, seg_query(id<<1, l, r));
        if (m < r) rt = max(rt, seg_query(id<<1|1, l, r));
        return rt;
    }

    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int,int> mp;
        for (int i=0; i<target.size(); i++) {
            mp[target[i]] = i+1;
        }
        seg_build(1, 0, target.size());
        int con = 0;
        for (int i:arr) {
            if(mp.count(i)) {
                int t = seg_query(1, 0, mp[i]-1)+1;
                con = max(con, t);
                seg_update(1, mp[i], t);
            }
        }
        return target.size()-con;
    }
};