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

发表于 更新于 分类于 ，

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

LeetCode1713

1
2
3
4
5
6
7
8
9
10
11
示例 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


解析

要求把一个数组变成另一个数组的子序列的最少操作次数，实际上可以转化为求两个数组的最长公共子序列问题。通常的最长公共子序列问题可以采用动态规划来解决：

\[ dp[i][j]=\begin{cases}dp[i-1][j-1]+1,a_1[i-1]=a_2[j-1]\\ max(dp[i-1][j],dp[i][j-1]),a_1[i-1]\neq a_2[j-1] \end{cases} \]

此时时间复杂度为\(O(n*m)\)​​ ,简要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def longestCommonSubsequence(text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]

进阶方法

有没有一种能够再次缩减时间复杂度的方式呢？当然是有的。注意到题中所给的条件，target中的元素是互不相同的，所以可以说它们和它们的下标是一一对应的。于是我们可以遍历arr数组，当其中有与target相等的元素时，用target中相应元素的下标索引来作为当前值，没有时跳过，这样可以得到一个新的数组，这样的数组中的最大递增子序列的长度就是两个数组的最大公共子序列的长度。(由于新数组由target的索引组成，作为target的子序列，新数组必定递增)。原来的问题就转化为一个求最大递增子序列的长度的问题。将最大递增子序列的长度求出来后用target的长度减去这个最大递增子序列的长度就可以得到最少的操作次数。

image-20210726211253413
image-20210726211253413

我们可以从此得出一个结论：当其中一个数组元素各不相同时，最长公共子序列问题（LCS）可以转换为最长上升子序列问题（LIS）进行求解。

而数组的最长递增子序列问题我们朴素的解法也是用动态规划求解： \(dp[i] = max(dp[i], dp[j] + 1),0≤j<i\)

其时间复杂度为\(O(n^2)\)，如此一来时间复杂度上没有任何优势，当然不能用此解法。这里需要用一种贪心+二分查找的方式来优化时间复杂度。

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。因此我们可以维护一个数组minEnd，minEnd[i-1]表示子序列长度为i时，其为最小的结尾元素。遍历arr数组，当arr[i]>minEnd[end]时，将arr[i]添加到minEnd的末尾，如果arr[i]<minEnd[end]则采用二分法将其插入到minEnd中合适的位置(arr[i]>minEnd[x]则minEnd[x+1]=arr[i])。最终最大递增子序列的长度即为minEnd数组的长度。此方式的时间复杂度为\(O(m+nlog(n))\)，其中\(m\)是target数组的长度，\(n\)​是arr数组的长度。实现实例如下：

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
def minOperations(target, arr) -> int:
    hashSet = dict()
    for i in range(len(target)): # target数组转化为索引
        if target[i] not in hashSet:
            hashSet[target[i]] = i

    lift_a = []
    for i in arr: # 以索引值更新arr数组
        if i in hashSet:
            lift_a.append(hashSet[i])

    if lift_a == []:
        return len(target)
    d = []
    d.append(lift_a[0])
    for i in range(1, len(lift_a)): # 二分查找更新
        left = 0
        right = len(d) - 1
        if d[-1] < lift_a[i]:
            d.append(lift_a[i])
            continue
        while left < right:
            middle = left + (right - left) // 2
            if d[middle] >= lift_a[i]:
                right = middle
            else:
                left = middle + 1
        d[right] = lift_a[i]
    return len(target) - len(d)


if __name__ == '__main__':
    print(minOperations([6, 4, 8, 1, 3, 2], [4, 7, 6, 2, 3, 8, 6, 1]))

[out]:
    3 # 最少需要操作三次