分析思路
对两个等长数组a、b,从前向后考虑,分别用指针i、j指向数组a、b。如果当前两元素相同,那么可以把这两个元素彻底删除掉。以后再也不用考虑。如果两元素不相同,考虑如何处理?
为了保证让a[i]等于b[j],只需要按照操作,把值为b[j]的元素从后面(在数组a中位置i后面的某个位置)提上来,提到a[i]前面一个位置,此时更新答案。但是不需要真正的做提取操作,提取操作的本质不改变后续元素的顺序性,所以这里用一个bool数组标记一下即可。后面指针i遇到值为b[j]的项,直接跳过即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
bool st[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
int i = 0, j = 0, ans = 0;
while(j < n) {
if(st[a[i]]) {
i++;
continue;
}
if(a[i] != b[j]) {
st[b[j]] = true;
ans++;
j++;
} else {
i++, j++;
}
}
printf("%d", ans);
return 0;
}