Hard

题目描述

给你一个由不同整数组成的数组 target 和另一个可以包含重复元素的整数数组 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^5
  • 1 <= target[i], arr[i] <= 10^9
  • target 不包含重复元素。

解题思路

这个问题可以转化为求最长公共子序列（LCS）问题，但由于 target 数组中的元素都是不同的，我们可以进行优化。

核心思路：

  1. 由于 target 中元素不重复，我们可以将其视为一个排列，为每个元素分配一个位置索引
  2. 将 arr 中的元素替换为它们在 target 中对应的索引位置
  3. 这样问题就转化为在新的数组中求最长递增子序列（LIS）
  4. 最少操作次数 = target 的长度 - 最长公共子序列的长度

算法步骤：

  1. 用哈希表记录 target 中每个元素的索引位置
  2. 遍历 arr，将存在于 target 中的元素替换为其索引，构建新数组 indices
  3. 在 indices 中求最长递增子序列的长度（使用二分查找优化到 O(n log n)）
  4. 返回 target.length - LIS长度

这种方法将时间复杂度优化到了 O(n log n)，比传统的 LCS 算法的 O(mn) 更高效。

推荐解法：使用二分查找的最长递增子序列算法，时间复杂度最优。

代码实现

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> pos;
        for (int i = 0; i < target.size(); i++) {
            pos[target[i]] = i;
        }
        
        vector<int> indices;
        for (int num : arr) {
            if (pos.count(num)) {
                indices.push_back(pos[num]);
            }
        }
        
        // 求最长递增子序列
        vector<int> lis;
        for (int idx : indices) {
            auto it = lower_bound(lis.begin(), lis.end(), idx);
            if (it == lis.end()) {
                lis.push_back(idx);
            } else {
                *it = idx;
            }
        }
        
        return target.size() - lis.size();
    }
};

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        from bisect import bisect_left
        
        pos = {num: i for i, num in enumerate(target)}
        
        indices = []
        for num in arr:
            if num in pos:
                indices.append(pos[num])
        
        # 求最长递增子序列
        lis = []
        for idx in indices:
            left = bisect_left(lis, idx)
            if left == len(lis):
                lis.append(idx)
            else:
                lis[left] = idx
        
        return len(target) - len(lis)

public class Solution {
    public int MinOperations(int[] target, int[] arr) {
        Dictionary<int, int> pos = new Dictionary<int, int>();
        for (int i = 0; i < target.Length; i++) {
            pos[target[i]] = i;
        }
        
        List<int> indices = new List<int>();
        foreach (int num in arr) {
            if (pos.ContainsKey(num)) {
                indices.Add(pos[num]);
            }
        }
        
        // 求最长递增子序列
        List<int> lis = new List<int>();
        foreach (int idx in indices) {
            int left = BinarySearch(lis, idx);
            if (left == lis.Count) {
                lis.Add(idx);
            } else {
                lis[left] = idx;
            }
        }
        
        return target.Length - lis.Count;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {number}
 */
var minOperations = function(target, arr) {
    const targetMap = new Map();
    for (let i = 0; i < target.length; i++) {
        targetMap.set(target[i], i);
    }
    
    const indices = [];
    for (const num of arr) {
        if (targetMap.has(num)) {
            indices.push(targetMap.get(num));
        }
    }
    
    const lis = [];
    for (const idx of indices) {
        let left = 0, right = lis.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (lis[mid] < idx) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left === lis.length) {
            lis.push(idx);
        } else {
            lis[left] = idx;
        }
    }
    
    return target.length - lis.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)其中 n 是 arr 的长度，构建哈希表 O(m)，遍历 arr O(n)，LIS 算法 O(n log n)
空间复杂度O(m + n)哈希表存储 target 元素位置 O(m)，indices 数组 O(n)，LIS 数组最多 O(min(m,n))

相关题目