class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
}
};
1713. 得到子序列的最少操作次数
给你一个数组 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 不包含任何重复元素。原站题解
java 解法, 执行用时: 56 ms, 内存消耗: 58 MB, 提交时间: 2023-06-05 14:19:13
class Solution {
public int minOperations(int[] target, int[] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0;i<target.length;i++)
map.put(target[i], i);
ArrayList<Integer> stack = new ArrayList<>();
for(int num:arr){
Integer idx = map.get(num);
if(idx != null){
int l=0,r=stack.size();
while(l<r){
int mid = l + r >> 1;
if(stack.get(mid) >= idx)
r = mid;
else
l = mid + 1;
}
if(l == stack.size())
stack.add(idx);
else
stack.set(l, idx);
}
}
return target.length - stack.size();
}
}
python3 解法, 执行用时: 216 ms, 内存消耗: 40.6 MB, 提交时间: 2023-06-05 14:18:52
class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
# 分析:
# 本题要找最少操作次数，实际上就是找最长的公共子序列(这样需要的操作最少)
# 根据target中互不相同，我们知道每个数字对应的坐标唯一
# 于是最长公共子序列等价于arr用target的坐标转换后构成最长的上升子序列
# 数字对应坐标
idx_dict = {num: i for i, num in enumerate(target)}
# 300.最长上升子序列
stack = []
for num in arr:
# 只有在target的数字才可能属于公共子序列
if num in idx_dict:
# 转换坐标
idx = idx_dict[num]
# 该坐标在当前栈中的位置
i = bisect.bisect_left(stack, idx)
# 如果在最后要加入元素，否则要修改该位置的元素
# 跟一般的讲，i代表了目前这个idx在stack中的大小位置，
# 在前面出现还比idx大的stack中的元素是无法和idx构成最长上升子序列的。
# i左边的数比idx小，可以和idx构成上升子序列，(idx构成的长度就是i+1)
# idx比i的值小，将i替换后可以方便后面构成更优的子序列(越小后面能加入的数越多)
if i == len(stack):
stack.append(0)
stack[i] = idx
# 最终stack的长度就构成了最长上升子序列的长度，用减法即可得到本题答案
return len(target) - len(stack)
java 解法, 执行用时: 90 ms, 内存消耗: 59.4 MB, 提交时间: 2023-06-05 14:18:32
class Solution {
public int minOperations(int[] target, int[] arr) {
int n = target.length;
Map<Integer, Integer> pos = new HashMap<Integer, Integer>();
for (int i = 0; i < n; ++i) {
pos.put(target[i], i);
}
List<Integer> d = new ArrayList<Integer>();
for (int val : arr) {
if (pos.containsKey(val)) {
int idx = pos.get(val);
int it = binarySearch(d, idx);
if (it != d.size()) {
d.set(it, idx);
} else {
d.add(idx);
}
}
}
return n - d.size();
}
public int binarySearch(List<Integer> d, int target) {
int size = d.size();
if (size == 0 || d.get(size - 1) < target) {
return size;
}
int low = 0, high = size - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (d.get(mid) < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
javascript 解法, 执行用时: 172 ms, 内存消耗: 71.1 MB, 提交时间: 2023-06-05 14:18:14
/**
* @param {number[]} target
* @param {number[]} arr
* @return {number}
*/
var minOperations = function(target, arr) {
const n = target.length;
const pos = new Map();
for (let i = 0; i < n; ++i) {
pos.set(target[i], i);
}
const d = [];
for (const val of arr) {
if (pos.has(val)) {
const idx = pos.get(val);
const it = binarySearch(d, idx);
if (it !== d.length) {
d[it] = idx;
} else {
d.push(idx);
}
}
}
return n - d.length;
};
const binarySearch = (d, target) => {
const size = d.length;
if (size === 0 || d[size - 1] < target) {
return size;
}
let low = 0, high = size - 1;
while (low < high) {
const mid = Math.floor((high - low) / 2) + low;
if (d[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
golang 解法, 执行用时: 144 ms, 内存消耗: 12.3 MB, 提交时间: 2023-06-05 14:17:54
func minOperations(target, arr []int) int {
n := len(target)
pos := make(map[int]int, n)
for i, val := range target {
pos[val] = i
}
d := []int{}
for _, val := range arr {
if idx, has := pos[val]; has {
if p := sort.SearchInts(d, idx); p < len(d) {
d[p] = idx
} else {
d = append(d, idx)
}
}
}
return n - len(d)
}