题目描述
给你一个数组 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(mn)$，无法通过本题，需要转变思路。
我们可以用一个哈希表记录 target 数组中每个元素的下标，然后遍历 arr 数组，对于 arr 数组中的每个元素，如果哈希表中存在该元素，则将该元素的下标加入到一个数组中，这样就得到了一个新的数组 nums，该数组是 arr 中的元素在 target 数组中的下标（去掉了不在 target 中的元素），该数组的最长递增子序列的长度就是 target 和 arr 的最长公共子序列的长度。
因此，问题转化为求 nums 数组的最长递增子序列的长度。参考 300. 最长递增子序列。
时间复杂度 $O(n\log n)$，其中 $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
37
38
39 | 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
|
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 | 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;
}
}
|
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
51
52
53
54
55
56
57
58
59
60 | 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;
}
};
|
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 | 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
}
|