Question

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

English Version

题目描述

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

解法

方法一：最长递增子序列

根据题意，target 和 arr 这两个数组的公共子序列越长，需要添加的元素就越少。因此，最少添加的元素个数等于 target 的长度减去 target 和 arr 的最长公共子序列的长度。

但是，求最长公共子序列的时间复杂度为 $O(mn)$，无法通过本题，需要转变思路。

我们可以用一个哈希表记录 target 数组中每个元素的下标，然后遍历 arr 数组，对于 arr 数组中的每个元素，如果哈希表中存在该元素，则将该元素的下标加入到一个数组中，这样就得到了一个新的数组 nums，该数组是 arr 中的元素在 target 数组中的下标（去掉了不在 target 中的元素），该数组的最长递增子序列的长度就是 target 和 arr 的最长公共子序列的长度。

因此，问题转化为求 nums 数组的最长递增子序列的长度。参考 300. 最长递增子序列。

时间复杂度 $O(n\log n)$，其中 $n$ 为 arr 数组的长度。

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  @staticmethod
  def lowbit(x):
    return x & -x

  def update(self, x, val):
    while x <= self.n:
      self.c[x] = max(self.c[x], val)
      x += BinaryIndexedTree.lowbit(x)

  def query(self, x):
    s = 0
    while x:
      s = max(s, self.c[x])
      x -= BinaryIndexedTree.lowbit(x)
    return s


class Solution:
  def minOperations(self, target: List[int], arr: List[int]) -> int:
    d = {v: i for i, v in enumerate(target)}
    nums = [d[v] for v in arr if v in d]
    return len(target) - self.lengthOfLIS(nums)

  def lengthOfLIS(self, nums):
    s = sorted(set(nums))
    m = {v: i for i, v in enumerate(s, 1)}
    tree = BinaryIndexedTree(len(m))
    ans = 0
    for v in nums:
      x = m[v]
      t = tree.query(x - 1) + 1
      ans = max(ans, t)
      tree.update(x, t)
    return ans

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    this.c = new int[n + 1];
  }

  public static int lowbit(int x) {
    return x & -x;
  }

  public void update(int x, int val) {
    while (x <= n) {
      c[x] = Math.max(c[x], val);
      x += lowbit(x);
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s = Math.max(s, c[x]);
      x -= lowbit(x);
    }
    return s;
  }
}

class Solution {
  public int minOperations(int[] target, int[] arr) {
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < target.length; ++i) {
      d.put(target[i], i);
    }
    List<Integer> nums = new ArrayList<>();
    for (int i = 0; i < arr.length; ++i) {
      if (d.containsKey(arr[i])) {
        nums.add(d.get(arr[i]));
      }
    }
    return target.length - lengthOfLIS(nums);
  }

  private int lengthOfLIS(List<Integer> nums) {
    TreeSet<Integer> ts = new TreeSet();
    for (int v : nums) {
      ts.add(v);
    }
    int idx = 1;
    Map<Integer, Integer> d = new HashMap<>();
    for (int v : ts) {
      d.put(v, idx++);
    }
    int ans = 0;
    BinaryIndexedTree tree = new BinaryIndexedTree(nums.size());
    for (int v : nums) {
      int x = d.get(v);
      int t = tree.query(x - 1) + 1;
      ans = Math.max(ans, t);
      tree.update(x, t);
    }
    return ans;
  }
}

class BinaryIndexedTree {
public:
  int n;
  vector<int> c;

  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int val) {
    while (x <= n) {
      c[x] = max(c[x], val);
      x += lowbit(x);
    }
  }

  int query(int x) {
    int s = 0;
    while (x > 0) {
      s = max(s, c[x]);
      x -= lowbit(x);
    }
    return s;
  }

  int lowbit(int x) {
    return x & -x;
  }
};

class Solution {
public:
  int minOperations(vector<int>& target, vector<int>& arr) {
    unordered_map<int, int> d;
    for (int i = 0; i < target.size(); ++i) d[target[i]] = i;
    vector<int> nums;
    for (int i = 0; i < arr.size(); ++i) {
      if (d.count(arr[i])) {
        nums.push_back(d[arr[i]]);
      }
    }
    return target.size() - lengthOfLIS(nums);
  }

  int lengthOfLIS(vector<int>& nums) {
    set<int> s(nums.begin(), nums.end());
    int idx = 1;
    unordered_map<int, int> d;
    for (int v : s) d[v] = idx++;
    BinaryIndexedTree* tree = new BinaryIndexedTree(d.size());
    int ans = 0;
    for (int v : nums) {
      int x = d[v];
      int t = tree->query(x - 1) + 1;
      ans = max(ans, t);
      tree->update(x, t);
    }
    return ans;
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
  return x & -x
}

func (this *BinaryIndexedTree) update(x, val int) {
  for x <= this.n {
    if this.c[x] < val {
      this.c[x] = val
    }
    x += this.lowbit(x)
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    if s < this.c[x] {
      s = this.c[x]
    }
    x -= this.lowbit(x)
  }
  return s
}

func minOperations(target []int, arr []int) int {
  d := map[int]int{}
  for i, v := range target {
    d[v] = i
  }
  nums := []int{}
  for _, v := range arr {
    if i, ok := d[v]; ok {
      nums = append(nums, i)
    }
  }
  return len(target) - lengthOfLIS(nums)
}

func lengthOfLIS(nums []int) int {
  s := map[int]bool{}
  for _, v := range nums {
    s[v] = true
  }
  t := []int{}
  for v := range s {
    t = append(t, v)
  }
  sort.Ints(t)
  d := map[int]int{}
  for i, v := range t {
    d[v] = i + 1
  }
  tree := newBinaryIndexedTree(len(d))
  ans := 0
  for _, v := range nums {
    x := d[v]
    t := tree.query(x-1) + 1
    ans = max(ans, t)
    tree.update(x, t)
  }
  return ans
}