AcWing 496. 机器翻译
原题链接
简单
作者:
ywt51
,
2023-06-06 12:46:32
,
所有人可见
,
阅读 130
算法1:数组模拟队列(枚举) $O(n)$
//数组标记是否出现,队列维护当前在内存中的单词
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int q[N], hh = 1, tt, st[N];
int n, m, res, x;
int main() {
cin >> m >> n;
while (n--) {
cin >> x;
if (st[x]) continue;
res++; //查询
st[x] = 1; //标记出现了
if (tt-hh+1 == m) {
st[q[hh]] = 0; //队头出队
hh++;
}
q[++tt] = x;
}
cout << res;
return 0;
}
算法2:stl-queue() $O(n)$
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int n, m, cnt;
int st[1010]; //哈希表
int main() {
cin >> m >> n;
while (n--) {
int x;
cin >> x;
if (!st[x]) {
cnt++;
st[x] = 1;
q.push(x);
if (q.size() == m+1) {
st[q.front()] = 0;
q.pop();
}
}
}
cout << cnt;
return 0;
}