题目描述
给你一个数组 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 <= 1051 <= target[i], arr[i] <= 109target 不包含任何重复元素。
解法
方法一：最长递增子序列 + 树状数组
根据题意，target 和 arr 这两个数组的公共子序列越长，需要添加的元素就越少。因此，最少添加的元素个数等于 target 的长度减去 target 和 arr 的最长公共子序列的长度。
但是，求最长公共子序列的时间复杂度为 $O(m \times n)$，无法通过本题，需要转变思路。
我们可以用一个哈希表记录 target 数组中每个元素的下标，然后遍历 arr 数组，对于 arr 数组中的每个元素，如果哈希表中存在该元素，则将该元素的下标加入到一个数组中，这样就得到了一个新的数组 nums，该数组是 arr 中的元素在 target 数组中的下标（去掉了不在 target 中的元素），该数组的最长递增子序列的长度就是 target 和 arr 的最长公共子序列的长度。
因此，问题转化为求 nums 数组的最长递增子序列的长度。参考 300. 最长递增子序列。
时间复杂度 $O(n \times \log m)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别为 target 和 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 | class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
res = 0
while x:
res = max(res, self.c[x])
x -= x & -x
return res
class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
d = {x: i for i, x in enumerate(target, 1)}
nums = [d[x] for x in arr if x in d]
m = len(target)
tree = BinaryIndexedTree(m)
ans = 0
for x in nums:
v = tree.query(x - 1) + 1
ans = max(ans, v)
tree.update(x, v)
return len(target) - ans
|
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
37
38
39
40
41
42
43
44
45
46
47 | class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
this.c = new int[n + 1];
}
public void update(int x, int v) {
for (; x <= n; x += x & -x) {
c[x] = Math.max(c[x], v);
}
}
public int query(int x) {
int ans = 0;
for (; x > 0; x -= x & -x) {
ans = Math.max(ans, c[x]);
}
return ans;
}
}
class Solution {
public int minOperations(int[] target, int[] arr) {
int m = target.length;
Map<Integer, Integer> d = new HashMap<>(m);
for (int i = 0; i < m; i++) {
d.put(target[i], i + 1);
}
List<Integer> nums = new ArrayList<>();
for (int x : arr) {
if (d.containsKey(x)) {
nums.add(d.get(x));
}
}
BinaryIndexedTree tree = new BinaryIndexedTree(m);
int ans = 0;
for (int x : nums) {
int v = tree.query(x - 1) + 1;
ans = Math.max(ans, v);
tree.update(x, v);
}
return m - ans;
}
}
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49 | class BinaryIndexedTree {
private:
int n;
vector<int> c;
public:
BinaryIndexedTree(int n)
: n(n)
, c(n + 1) {}
void update(int x, int v) {
for (; x <= n; x += x & -x) {
c[x] = max(c[x], v);
}
}
int query(int x) {
int ans = 0;
for (; x > 0; x -= x & -x) {
ans = max(ans, c[x]);
}
return ans;
}
};
class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
int m = target.size();
unordered_map<int, int> d;
for (int i = 0; i < m; ++i) {
d[target[i]] = i + 1;
}
vector<int> nums;
for (int x : arr) {
if (d.contains(x)) {
nums.push_back(d[x]);
}
}
BinaryIndexedTree tree(m);
int ans = 0;
for (int x : nums) {
int v = tree.query(x - 1) + 1;
ans = max(ans, v);
tree.update(x, v);
}
return m - ans;
}
};
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50 | type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
return BinaryIndexedTree{n: n, c: make([]int, n+1)}
}
func (bit *BinaryIndexedTree) Update(x, v int) {
for ; x <= bit.n; x += x & -x {
if v > bit.c[x] {
bit.c[x] = v
}
}
}
func (bit *BinaryIndexedTree) Query(x int) int {
ans := 0
for ; x > 0; x -= x & -x {
if bit.c[x] > ans {
ans = bit.c[x]
}
}
return ans
}
func minOperations(target []int, arr []int) int {
m := len(target)
d := make(map[int]int)
for i, x := range target {
d[x] = i + 1
}
var nums []int
for _, x := range arr {
if pos, exists := d[x]; exists {
nums = append(nums, pos)
}
}
tree := NewBinaryIndexedTree(m)
ans := 0
for _, x := range nums {
v := tree.Query(x-1) + 1
if v > ans {
ans = v
}
tree.Update(x, v)
}
return m - ans
}
|
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
37
38
39
40
41
42
43 | class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, v: number): void {
for (; x <= this.n; x += x & -x) {
this.c[x] = Math.max(this.c[x], v);
}
}
query(x: number): number {
let ans = 0;
for (; x > 0; x -= x & -x) {
ans = Math.max(ans, this.c[x]);
}
return ans;
}
}
function minOperations(target: number[], arr: number[]): number {
const m = target.length;
const d: Map<number, number> = new Map();
target.forEach((x, i) => d.set(x, i + 1));
const nums: number[] = [];
arr.forEach(x => {
if (d.has(x)) {
nums.push(d.get(x)!);
}
});
const tree = new BinaryIndexedTree(m);
let ans = 0;
nums.forEach(x => {
const v = tree.query(x - 1) + 1;
ans = Math.max(ans, v);
tree.update(x, v);
});
return m - ans;
}
|