题解 | #机器翻译#

对于这个题，通过老师的学习，有三种解法，要是让我自己做，肯定是做不出的。 第一种解法 因为数据的大小是0至1000，所以我们用一个数组vis，来记录一个数是否在内存中和存入内存的时间，如果不在内存中，在这个数被标记为0，因为内存的大小有限，所以最低层的数要不断更新，我们用min，来记录最底层的放入时间，因为一直在变化，所以我们每一次将min=i，直接设为当前最大的时间，来进行查找最小的时间，（这是一个难点），找到之后，我们要进行更新，我们要将之前最底层的那个数进行删除掉，设为0，然后给刚查找的值，赋值为进来的时间。这就是这个解法的大致过程，直接使用的是暴力解法，时间复杂度为O(n*1000)，对于数据较多的情况不适用。

#include<bits/stdc++.h>
using namespace std;
int vis[1010]; 
int main()
{
    int m,n;
    int pos;
    cin>>m>>n;
    int a,check=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(vis[a]!=0) continue;
        check++;
        if(m>0)
        {
            vis[a]=i;
            m--;
        }
        else
        {
            int min=i;
            for(int j=0;j<=1000;j++)
            {
                if(vis[j]!=0&&vis[j]<min)
                {
                    min=vis[j],pos=j;
                 
                }
            }
            vis[pos]=0;
            vis[a]=i;
             
        }
         
     } 
     cout<<check<<endl;
}

第二中解法是用队列的思想，将输入的全部数据看成一个有底面的水管，根据输入的内存的大小，锁定这个大小来进行移动，通俗的讲就是大水管中套一个小水管，先检查输入的新数据是否在这个小水管中，如果在，直接下一循环，如果不在，小水管进行移动，查询一次。这里有一个很细节的处理就是（++cnt),可以精确的定位，是目前小水管最靠后的定位，从 cnt=0，开始，避免了使用cnt++带来的思路不清晰。这种方法的时间复杂度是O(n*m).

#include<bits/stdc++.h>
using namespace std;
int m,n,x;
int a[1010];
int cnt;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        int flag=0;
        for(int j=cnt;j>=cnt-m+1&&j>=1;j--)
        {
            if(a[j]==x)
            {
                flag=1;
                break;
            }
        }
        if(flag==1) continue;
        a[++cnt]=x;
 
    }
    cout<<cnt;
    return 0;
}

第三种解法是，我个人认为是第二种解法的升级版，设置了两个数组，第一个数组是存储于大水管的数a，另一个数组的作用就相当于是一个小水管vis，如果输入的数使vis[]等于1，说明这个数在小水管内，如果输入的数使vis[]不等于1，那么我们就要进行更新，使这个新数等于1，另外之前最底层的数更新为0，因为小水管只有m个数，用当前这个cnt代表大水管最新的位置，也是小水管最新的位置，用cnt-m就知道最底层那个数的位置了，然后将他赋值为0，这个方法的时间复杂度为O（n).

#include<bits/stdc++.h>
using namespace std;
int m,n,x,cnt=0;
int a[1010];
int vis[1010];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(vis[x]==1) continue;
		a[++cnt]=x;
		vis[a[cnt]]=1;
        if(cnt>m)
		{
			vis[a[cnt-m]]=0;
				}		
	}
	cout<<cnt;
	return 0;
}