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

题目地址(1713. 得到子序列的最少操作次数)

https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/

题目描述

给你一个数组 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 不包含任何重复元素。

前置知识

• 动态规划

• LIS

公司

• 暂无

思路

这道题属于最长上升子序列的换皮题。关于最长上升子序列可以参考我之前写的文章穿上衣服我就不认识你了？来聊聊最长上升子序列

具体的思路为：

1. 新建一个空的列表 B

2. 遍历 arr， 如果 arr 中的数字存在于 target 中，将其索引添加到列表 B 中

3. 求列表的最长上升子序列的长度（典型算法），这个长度实际上就是我们可以利用 arr 中的数所能组成的 最长的 target 的子序列，换句话说，我们添加最少的数就可以构成 target。

4. 答案就是 target 的长度减去最长子序列的长度。

• 为了加快第 2 步的速度，可以建立 target 的反向索引方便能够在 $O(1)$ 时间根据 val 获取到索引。

• 由于这道题数据范围是 $10^5$，因此只能使用 $NlogN$ 的贪心才行。

关于为什么 10 ^ 5 就必须使用 $NlogN$ 甚至更优的算法我在刷题技巧提过。更多复杂度速查可参考我的刷题插件，公众号《力扣加加》回复插件获取即可

关键点

• LIS

代码

class Solution:
    def minOperations(self, target: List[int], A: List[int]) -> int:
        def LIS(A):
            d = []
            for a in A:
                i = bisect.bisect_left(d, a)
                if d and i < len(d):
                    d[i] = a
                else:
                    d.append(a)
            return len(d)
        B = []
        target = { t:i for i, t in enumerate(target)}
        for a in A:
            if a in target: B.append(target[a])
        return len(target) - LIS(B)

复杂度分析

• 时间复杂度：$O(max(BlogB, A))$。

• 空间复杂度：由于 target 大小大于 B 的大小，因此空间复杂度为 $O(target)$。

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。