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

7/26/2021 LCSLISLCS 2 LIS二分哈希表贪心LeetCode

给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arrarr 可能 包含重复元素。请你返回 最少 操作次数,使得 target 成为 arr 的一个子序列。

# 题目描述

给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arrarr 可能 包含重复元素。

每一次操作中,你可以在 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] 不是子序列。

1713. 得到子序列的最少操作次数 (opens new window)

# 示例

输入: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
2
3
4
5
6

# 提示

  • 1 <= target.length, arr.length <= 10^5
  • 1 <= target[i], arr[i] <= 10^9
  • target 不包含任何重复元素。

# 解法:Hash + LCS 2 LIS

# 解法1: DP

  • 时间复杂度:O(n+mlogm)\mathcal{O}(n+mlogm)
  • 空间复杂度:O(n+m)\mathcal{O}(n+m)

根据题意,是求最长公共子序列(Longest Common Subsequence,简称LCS)「1143. 最长公共子序列的官方题解 (opens new window)」。

但是该题目的数据量都过于大,不能在O(n^2)情况下解决,前提条件是目标数组target的元素不重复这就表示target中的每个元素都与其索引一一对应。可以利用这一特性加速查找过程。

因此考虑求LCS转化为求最长上升子序列(Longest Increasing Subsequence,简称LIS)。这也是一个经典问题,读者可以参考「300. 最长递增子序列的官方题解 (opens new window)」,使用贪心和二分查找的方法得到最长递增子序列的长度

核心思想是把target中的每个元素映射到其索引下标,忽略arr中存在但是target中不存在的数据,然后就可以求arr和target的LIS了。

func minOperations(target []int, arr []int) int {
    // 映射taget的位置和值
    idxs := make(map[int]int, len(target))
    for i, val := range target {
        idxs[val] = i
    }

    // 计算LIS
    LIS := make([]int, 0, len(target))
    for _, val := range arr {
        if i, ok := idxs[val]; ok {
            if p := sort.SearchInts(LIS, i); p < len(LIS) {
                LIS[p] = i
            } else {
                LIS = append(LIS, i)
            }
        }
    }

    return len(target) - len(LIS)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
上次更新于: a year ago