問題描述

給定一個包含 n 個整數的陣列，你的任務是從左到右，計算每個長度為 k 的子陣列中的 MEX 值

MEX（Minimum Excluded Value）是指在陣列中最小的沒出現的非負整數。

例如：3,1,4,3,0,5 的 MEX 為 2（因為 0、1 存在，但 2 不在陣列中）

練習題

連結：https://cses.fi/problemset/task/3219/

完整程式碼

對於任意大小為 k 的子陣列，其 MEX 的範圍為 0 ≤ MEX ≤ k(當0 ~ k-1都有)

我們可維護一個「可能」MEX 的候選名單，這個名單會由小排到大，因此我們每個子陣列只要輸出名單中最小的那個即可。

維護這個 MEX 的候選名單：

  1. 如果刪掉的那個被刪了之後，導致他所代表的數字從沒出現過，代表它所代表的數字可能是 MEX 候選人

  2. 如果加入的那個原本在 MEX 候選人裡面，要把他代表的數字從候選名單刪除

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n, k;
    cin >> n >> k;
    int arr[200005];
    for (int i = 0; i < n; i++) cin >> arr[i];
    map<int, int> freq;
    set<int> candidate;
    for (int i = 0; i <= k; i++) candidate.insert(i);
    for (int i = 0; i < k; i++) {
        freq[arr[i]]++;
        candidate.erase(arr[i]);
    }
    cout << *candidate.begin() << ' ';
    for (int i = k; i < n; i++) {
        int out = arr[i - k];
        int in = arr[i];
        freq[out]--;
        if (freq[out] == 0) {
            candidate.insert(out);
        }
        freq[in]++;
        if (candidate.find(in) != candidate.end()) {
            candidate.erase(in);
        }
        cout << *candidate.begin() << ' ';
    }
}