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

难度: Hard

给你一个数组 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 <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target 不包含任何重复元素。

Submission

运行时间: 149 ms

内存: 40.3 MB

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
            
        from bisect import bisect_left

        # 将 target 的值和索引映射起来
        target_index_map = {num: i for i, num in enumerate(target)}

        # 仅保留 arr 中存在于 target 中的元素，并转换为 target 中的索引
        lis = []
        for num in arr:
            if num in target_index_map:
                lis.append(target_index_map[num])

        # 通过贪心和二分查找方法求 LIS 的长度
        dp = []
        for i in lis:
            if not dp or i > dp[-1]:
                dp.append(i)
            else:
                idx = bisect_left(dp, i)
                dp[idx] = i

        # 最少操作次数为 target 长度减去 LIS 的长度
        return len(target) - len(dp)

Explain

该题解采用了贪心算法和最长递增子序列（LIS）的概念。首先，创建一个映射将 target 中的值和其索引关联起来。然后，遍历 arr 数组，保留那些在 target 中出现的元素，并将它们转换为在 target 中的索引，存入一个新的数组 lis 中。接下来，利用贪心和二分查找的方法来找出 lis 中的最长递增子序列的长度。最后，由于 target 是一个没有重复元素的数组，且要求 arr 的子序列与 target 相同，因此 arr 至少需要添加的元素个数等于 target 的长度减去 lis 的最长递增子序列的长度。

时间复杂度: O(n + m logk)

空间复杂度: O(n + k)

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        
        from bisect import bisect_left

        # 将 target 的值和索引映射起来
        target_index_map = {num: i for i, num in enumerate(target)}

        # 仅保留 arr 中存在于 target 中的元素，并转换为 target 中的索引
        lis = []
        for num in arr:
            if num in target_index_map:
                lis.append(target_index_map[num])

        # 通过贪心和二分查找方法求 LIS 的长度
        dp = []
        for i in lis:
            if not dp or i > dp[-1]:
                dp.append(i)
            else:
                idx = bisect_left(dp, i)
                dp[idx] = i

        # 最少操作次数为 target 长度减去 LIS 的长度
        return len(target) - len(dp)

Explore

在此题解中，将arr数组中的元素转换为它们在target中的索引是为了简化问题，使其转变为寻找最长递增子序列的问题。这种转换是必要的，因为我们的目标是找到arr中与target相匹配的最长子序列。通过将target的元素映射到它们的索引，我们可以将问题转化为在这些索引上寻找最长递增子序列。这样一来，任何在arr中以递增顺序排列的索引序列都直接对应于target中的一个有效子序列，这样可以有效地利用已有的LIS算法来解决问题。

在处理LIS问题时，使用二分查找方法来更新dp数组可以显著提高算法的效率。传统的LIS算法通过遍历每个元素并与dp数组中的所有元素进行比较，其时间复杂度为O(n^2)。然而，通过使用二分查找来确定元素插入的位置，可以将每个元素的更新时间减少到O(log n)，从而将整体时间复杂度降低到O(n log n)。这种方法允许我们快速找到并更新dp数组中的最小可能值，以保持dp数组长度的有效性，即随时维护最长递增子序列的最优长度。

在给定的解法中，dp数组的最终长度代表了在arr中找到的最长递增子序列（该子序列对应于target中的索引）的长度。这个长度是关键，因为它直接决定了为使arr的子序列与target相匹配所需的最少操作次数。具体来说，最少操作次数等于target的长度减去dp数组的长度。这是因为dp数组的长度表示无需任何修改即可从arr中得到的与target相匹配的最大子序列长度，因此剩余的元素需要通过添加操作来补齐以形成完整的target序列。

如果arr数组完全不包含target数组中的任何元素，那么在将arr元素转换为target索引的过程中，lis数组将为空，因为没有任何arr元素可以映射到target的索引上。因此，dp数组也将为空，因为没有元素可以用来形成递增序列。在这种情况下，dp数组的长度为0，根据算法的逻辑，最少操作次数将等于target的长度（即len(target) - 0），因为需要将整个target数组作为子序列插入到arr中以满足题目要求。