arrays - MEX 大于或等于 k ​​的最小长度子数组

Question

给定一个大小为 N 的数组 A。找到 MEX 值大于或等于 K 的最小子数组。

MEX：最小排除值

我只是想了解解决它的算法。

标签： arraysdata-structures

Answer 1

您可以使用带有滑动窗口技术的二进制搜索。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool go(int mp[],int k)
{
    for(int i=0;i<k;i++)
    {
        if(mp[i]==0)
            return false;
    }
    return true;
}

bool check(vector<int> &a,int m,int k)
{
    int mp[1002]={0};
    for(int i=0;i<m-1;i++)
        mp[a[i]]++;
    for(int i=m-1;i<a.size();i++)
    {
        mp[a[i]]++;
        if(go(mp,k))
            return true;
        mp[a[i-m+1]]--;
    }
    return false;
}

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    int low=k,high=n,ans=1e9;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(check(a,mid,k))
        {
            ans=min(ans,mid);
            high=mid-1;
        }
        else
            low=mid+1;
    }
    cout<<(ans==1e9?-1:ans)<<'\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();

    return 0;
    
}

输出：

5 3
4 2 4 1 0