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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
// 1713. Minimum Operations to Make a Subsequence
#include "leetcode.h"
/*
* given an array 'target' that consists of distinct integers and another
* integer array 'arr' that can have duplicates. in one operatioin, you can
* insert any integer at any position in 'arr'. note that you can inser the
* integer at the very beginning or end of the array. return the minimum number
* of operations needed to make 'target' a subsequence of 'arr'. a subsequence
* of anarray is a new array generated from the original array by deleting some
* elements (possibly none) without changing the remaining elements.
*/
int cmp(const void *a, const void *b) {
int *a1 = *(int **)a;
int *b1 = *(int **)b;
return a1[1] - b1[1];
}
int binary_search(int *nums, int n, int val) {
int left = 0, right = n - 1, mid;
if (val <= nums[0])
return 0;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] == val)
return mid;
if (nums[mid] > val)
right = mid;
else
left = mid + 1;
}
return left;
}
int bfs(int **nums, int n, int val) {
int left = 0, right = n - 1, mid;
if (val < nums[0][1] || val > nums[n - 1][1])
return -1;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid][1] == val)
return nums[mid][0];
if (nums[mid][1] > val)
right = mid - 1;
else
left = mid + 1;
}
if (nums[left][1] == val)
return nums[left][0];
return -1;
}
int minOperations(int *target, int targetSize, int *arr, int arrSize) {
int t = targetSize, a = arrSize, idx = 0;
int **copy_target = (int **)malloc(t * sizeof(int *));
for (int i = 0; i < t; i++) {
copy_target[i] = malloc(2 * sizeof(int));
copy_target[i][0] = i;
copy_target[i][1] = target[i];
}
qsort(copy_target, t, sizeof(int *), cmp);
for (int i = 0; i < a; i++) {
int pos = bfs(copy_target, t, arr[i]);
if (pos != -1) {
arr[idx] = pos;
idx++;
}
}
if (!idx)
return t;
int *stack = (int *)malloc(idx * sizeof(int));
stack[0] = arr[0];
int s_idx = 1;
for (int i = 1; i < idx; i++)
if (arr[i] > stack[s_idx - 1]) {
stack[s_idx] = arr[i];
s_idx++;
} else {
int x = binary_search(stack, s_idx, arr[i]);
stack[x] = arr[i];
}
free(copy_target), free(stack);
return t - s_idx;
}
int main() {
int t1[] = {5, 1, 3}, t2[] = {6, 4, 8, 1, 3, 2}, a1[] = {9, 4, 2, 3, 4},
a2[] = {4, 7, 6, 2, 3, 8, 6, 1};
printf("%d\n",
minOperations(t1, ARRAY_SIZE(t1), a1, ARRAY_SIZE(a1))); // expect: 2
printf("%d\n",
minOperations(t2, ARRAY_SIZE(t2), a2, ARRAY_SIZE(a2))); // expect: 3
}
|