$\href{}{\Huge\color{#4682B4}{数据结构 \ 队列(queue)}}$
5
算法1
(模拟,队列) $O(n)$
这道题目其实就是有$n$个东西,现在有一个容量为$m$的容器,要往里面放东西,如果放的东西大于这个容器的容量,就把最先放到容器里的东西拿出来。最后求出放进去了多少个东西。
这个容器其实就是队列,那我们的思路就是:
建立一个队列
每次读入一个单词,如果这个单词在队列里没出现过,且队列容量足够,把这个单词压入队列,计数器加1
如果队列里的单词大于队列容量,弹出队头
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int N = 1000;
int m,n;
class Queue{ // 手写队列
public:
int q[N],head = 0,tail = 0;
void init(){ // 初始化
tail = -1;
}
void push(int x){ // 往队列里压入一个数
q[++ tail] = x;
}
void pop(){ // 弹出
head ++;
}
int find(int x){ // 在队列里寻找数x
for(int i = head;i <= tail;i ++){
if(q[i] == x) return i;
}
return -1;
}
int size(){ // 队列长度
return tail - head + 1;
}
};
int main(){
int ans = 0; // 计数器
scanf("%d%d",&m,&n); // m为容器容量,n为文章长度
Queue q; // 队列
q.init(); // 初始化
for(int i = 1;i <= n;i ++){ // 读入文章并操作
int x; // 当前单词
scanf("%d",&x);
if(q.find(x) == -1){ // 如果没有在队列中找到这个单词
q.push(x); // 把这个数压入队列
ans ++; // 计数器加一
}
if(q.size() > m) q.pop(); // 如果超过容量,弹出队头
}
printf("%d\n",ans); // 输出计数器
return 0;
}