Агуулгыг алгасах

Дарааллын MEX (хамгийн бага орхигдсон)

$N$ хэмжээтэй $A$ массив өгөгдсөн. Та массивт байхгүй хамгийн бага сөрөг биш элементийг олох ёстой. Энэ тоог түгээмэлээр MEX (хамгийн бага орхигдсон) гэж нэрлэдэг.

$$ \begin{align} \text{mex}(\{0, 1, 2, 4, 5\}) &= 3 \\ \text{mex}(\{0, 1, 2, 3, 4\}) &= 5 \\ \text{mex}(\{1, 2, 3, 4, 5\}) &= 0 \\ \end{align} $$

$N$ хэмжээтэй массивын MEX хэзээ ч $N$-ээс өөрөөс нь их байж чадахгүй гэдгийг анхаарна уу.

Хамгийн хялбар арга бол $A$ массив дахь бүх элементийн олонлог үүсгэх ба ингэснээр бид тоо массивын хэсэг эсэхийг хурдан шалгаж болно. Дараа нь бид $0$-ээс $N$ хүртэлх бүх тоог шалгаж, одоогийн тоо олонлогт байхгүй бол түүнийг буцаана.

Implementation

The following algorithm runs in $O(N \log N)$ time.

int mex(vector<int> const& A) {
    set<int> b(A.begin(), A.end());

    int result = 0;
    while (b.count(result))
        ++result;
    return result;
}

If an algorithm requires a $O(N)$ MEX computation, it is possible by using a boolean vector instead of a set. Notice, that the array needs to be as big as the biggest possible array size.

int mex(vector<int> const& A) {
    static bool used[MAX_N+1] = { 0 };

    // mark the given numbers
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = true;
    }

    // find the mex
    int result = 0;
    while (used[result])
        ++result;

    // clear the array again
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = false;
    }

    return result;
}

This approach is fast, but only works well if you have to compute the MEX once. If you need to compute the MEX over and over, e.g. because your array keeps changing, then it is not effective. For that, we need something better.

Массив шинэчлэлттэй MEX

Энэ бодлогод та массив дахь тус бүрийн тоог өөрчлөх ба ийм шинэчлэл бүрийн дараа массивын шинэ MEX-ийг тооцоолох хэрэгтэй.

Ийм асуулгуудыг үр ашигтай боловсруулдаг илүү сайн өгөгдлийн бүтэц шаардлагатай.

Нэг арга бол $0$-ээс $N$ хүртэлх тоо бүрийн давтамжийг авч, түүн дээр модон төст өгөгдлийн бүтэц байгуулах явдал юм. Жишээ нь хэрчмийн мод эсвэл трип. Зангилаа бүр тоонуудын интервалыг төлөөлөх ба интервал дахь нийт давтамжийн хамт та тухайн интервал дахь ялгаатай тоонуудын тоог нэмж хадгална. Энэ өгөгдлийн бүтцийг $O(\log N)$ хугацаанд шинэчилж болох ба мөн MEX-ийн хувьд хоёртын хайлт хийснээр MEX-ийг $O(\log N)$ хугацаанд олж болно. Хэрэв $[0, \lfloor N/2 \rfloor)$ интервалыг төлөөлөх зангилаа $\lfloor N/2 \rfloor$ ширхэг ялгаатай тоо агуулаагүй бол нэг нь дутуу байгаа бөгөөд MEX нь $\lfloor N/2 \rfloor$-ээс бага тул та модны зүүн салбар руу рекурс хийж болно. Эс бөгөөс энэ нь дор хаяж $\lfloor N/2 \rfloor$ бөгөөд та модны баруун салбар руу рекурс хийж болно.

Мөн стандарт сангийн map ба set өгөгдлийн бүтцийг ашиглаж болно (энд тайлбарласан арга дээр үндэслэсэн). map-ээр бид тоо бүрийн давтамжийг санах ба set-ээр массиваас одоогоор дутагдаж буй тоонуудыг илэрхийлнэ. set эрэмбэлэгдсэн байдаг тул *set.begin() нь MEX болно. Нийтдээ бид $O(N \log N)$ урьдчилсан тооцоо хийх шаардлагатай ба үүний дараа MEX-ийг $O(1)$-д тооцоолж, шинэчлэлийг $O(\log N)$-д гүйцэтгэж болно.

class Mex {
private:
    map<int, int> frequency;
    set<int> missing_numbers;
    vector<int> A;

public:
    Mex(vector<int> const& A) : A(A) {
        for (int i = 0; i <= A.size(); i++)
            missing_numbers.insert(i);

        for (int x : A) {
            ++frequency[x];
            missing_numbers.erase(x);
        }
    }

    int mex() {
        return *missing_numbers.begin();
    }

    void update(int idx, int new_value) {
        if (--frequency[A[idx]] == 0)
            missing_numbers.insert(A[idx]);
        A[idx] = new_value;
        ++frequency[new_value];
        missing_numbers.erase(new_value);
    }
};

Дасгал бодлогууд