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

给你一个数组 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] 不是子序列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence

示例一

输入：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 <= 105
• 1 <= target[i], arr[i] <= 109
• target 不包含任何重复元素。

题解

该问题可转换为求最长公共子序列，找到两个数组的最长公共子序列的长度，然后target数组长度 - 公共序列长度即为所求
求解最长公共子序列：

• 1.我们可以先遍历target数组一次，记录target元素及其下标，
• 2.遍历arr数组，依次记录数组中出现target元素的次序【即arr当前元素在target数组中的下标】，结果存在index数组中
• 3.然后问题转为求index数组的最长递增子序列，动态规划即可解决，但本题数据规模较大，须采用贪心+二分查找
• 4.创建一个d数组，存放最长递增子序列，贪心即为，总是查找index中大于d[len]的最小值，将其纳入d数组中，遇到小于d[len]的值，则通过二分查找，找到第一个不大于index[i]的数，将index[i]放在该数的下一项.

AC代码

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        int m = target.size(), n = arr.size();
        unordered_map <int, int> map;
        vector <int> index;
        for(int i = 0; i < m; i++)
            map[target[i]] = i+1;//i+1是为了避免下标为0时造成的漏判
        for(int i = 0; i < n; i++)
            if(map[arr[i]])
                index.push_back(map[arr[i]]);//将arr中出现的target元素依次记录下来
        if(index.size() == 0)
            return m;//特殊情况判断，没有公共子序列,直接返回target数组的长度

        // 二分查找 arr 的最长递增子序列
        //如果index[i] > d[len] ，则直接加入到 d 数组末尾，并更新 d[len+1]=index[i]
        //否则，在 d 数组中二分查找，找到第一个比index[i]小的数d[k]，并更新d[k + 1]=index[i]。这一步的意思是长度为k+1的公共子序列的末尾元素的最小值更新为index[i]

        n = index.size();
        int len = 1;
        vector<int> d(n + 1, 0);
        d[len] = index[0];
        for (int i = 1; i < n; ++i) 
        {
            if (index[i] > d[len])
                d[++len] = index[i];
            else 
            {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 index[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) 
                {
                    int mid = (l + r) >> 1;
                    if (d[mid] < index[i]) 
                    {
                        pos = mid;
                        l = mid + 1;
                    } 
                    else
                        r = mid - 1;
                }
                d[pos + 1] = index[i];//在第一个比index[i]小的元素后面插入index[i]
            }
        }
        return m - len;
    }
};