Array-д байхгүй хамгийн бага сөрөг биш тоог олно.

Basic LevelХугацаа: O(n + max a)Санах ой: O(max a)

Эхлээд жижиг бодлого

a = [3, 0, 1, 5, 1, 2, 7] array-д байхгүй хамгийн бага сөрөг биш тоо хэд вэ?

0, 1, 2, 3 бүгд байна, харин 4 алга. Тиймээс MEX = 4. 5, 7 байгаа нь хариунд нөлөөлөхгүй.

Энгийн аргаас санаа руу

Энгийн арга: m = 0, 1, 2, … гэж явж, m бүрийг array-гээс бүхэлд нь хайна. m бүрт n алхам тул нийт n² орчим. n = 100 000 бол 10 тэрбум алхам, хэт удаан.

Гол санаа: эхлээд тоо бүрийг seen array-д нэг удаа тэмдэглэнэ. Тэгвэл seen[m]-ийг шалгах нь ганц алхам болно. Нийт 2n орчим алхам.

Нэр томьёо ба тэмдэглэгээ

MEX
Minimum excluded: олонлогт байхгүй хамгийн бага сөрөг биш тоо.
seen[x]
x тоо array-д байгаа эсэхийг хадгалах bool array.
m
Одоо шалгаж буй тоо. seen[m] тэмдэгтэй л бол нэгээр нэмэгдэнэ.
сөрөг биш тоо
0, 1, 2, … гэх мэт 0-ээс багагүй бүхэл тоо.
a
3
0
0
1
1
2
5
3
1
4
2
5
7
6
seen
0
1
2
3
4
5
6
7
8

MEX гэдэг нь array-д байхгүй хамгийн бага сөрөг биш тоо. Жишээ нь {0, 1, 3} бол MEX = 2. Эхлээд array-н тоо бүрийг seen array-д тэмдэглэе.

Алхам 1 / 13
Хурд
  • a[i] / m
  • Сая тэмдэглэсэн
  • Array-д байгаа тоо
  • MEX
Слайд 1 / 5

MEX гэж юу вэ?

MEX бол array-д байхгүй хамгийн бага сөрөг биш тоо. {0, 1, 2, 3, 5, 7} бол 4 алга тул MEX = 4. Тоглоомын онол, Grundy тоонд их хэрэглэгддэг.

mex.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
bool seen[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
seen[a[i]] = true;
}
int m = 0;
while (seen[m]) {
m++;
}
cout << m << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

MEX тоглоомын онол (Grundy тоо), олонлогийн бодлогод их гардаг. Array-г эрэмбэлэхгүйгээр n орчим алхамд олно.

Яаж ажилладаг вэ?

1. Array-н тоо бүрт seen[a[i]] = true гэж тэмдэглэнэ. 2. m = 0-ээс эхэлнэ. seen[m] тэмдэгтэй бол m-ийг нэгээр нэмнэ. 3. Тэмдэггүй эхний m бол хариу. n тоотой array-н MEX хэзээ ч n-ээс их болохгүй. Тиймээс n-ээс том тоонуудыг тоохгүй байж болно. Оролт: n, дараа нь n тоо.

Яагаад зөв, хэр хурдан бэ?

Loop seen[m] хоосон болмогц зогсдог. Тэр үед 0-ээс m − 1 хүртэлх бүх тоо тэмдэгтэй, m өөрөө тэмдэггүй. Энэ бол яг MEX-ийн тодорхойлолт.

n тоотой array-д 0-ээс n хүртэлх n + 1 тоо бүгд байх боломжгүй. Тиймээс MEX ≤ n, loop n + 1-ээс илүү эргэхгүй. Хугацаа O(n), санах ой O(n). n = 100 000 бол 200 000 орчим алхам.

Түгээмэл алдаа

  • Том тоог шүүхгүй орхих. a[i] нь 10⁹ хүртэл байж болох бол seen[a[i]] array-гээс гарна. if (a[i] <= n) нөхцөл нэмээрэй.
  • Сөрөг тоо: seen[-3] гэж бичвэл буруу санах ой руу хандана. Сөрөг тоог шууд алгас.
  • Олон test case-тэй бодлогод seen-ийг test бүрийн өмнө цэвэрлэхээ мартах. Зөвхөн ашигласан нүднүүдээ буцааж false болго.
  • MEX-ийг 1-ээс эхэлж хайх. MEX 0-ээс эхэлнэ: {1, 2, 3} бол хариу 0.

Хязгаарын тохиолдол

  • 0 байхгүй: seen[0] шууд хоосон тул loop нэг ч эргэхгүй, хариу 0.
  • Array нь яг 0, 1, …, n − 1: бүх тоо байгаа тул хариу n.
  • Бүх тоо ижил, жишээ нь [2, 2, 2]: зөвхөн seen[2] тэмдэгтэй, хариу 0.
  • n = 1, a = [0]: хариу 1.

Өөрийгөө шалга

  1. a = [1, 2, 3] бол MEX хэд вэ?

    Хариу харах

    0. 0 array-д алга.

  2. a = [0, 1, 2, 4, 5] бол MEX хэд вэ?

    Хариу харах

    3.

  3. 5 тоотой array-н MEX хамгийн ихдээ хэд байж болох вэ?

    Хариу харах

    5. Жишээ нь [0, 1, 2, 3, 4].

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [2, 0, 4, 1, 0, 6] дээр seen array ямар болохыг бичээд MEX-ийг ол.

    Hint харах

    Давхардсан 0 нэг л нүдийг тэмдэглэнэ.

    Хариу ба тайлбар

    seen[0], seen[1], seen[2], seen[4], seen[6] тэмдэгтэй. seen[3] хоосон тул MEX = 3.

  2. 2.a[i] нь 10⁹ хүртэл байж болох үед кодыг аюулгүй болго.

    Hint харах

    MEX хэзээ ч n-ээс их болохгүй гэдгийг ашигла.

    Хариу ба тайлбар

    Тэмдэглэхийн өмнө if (a[i] <= n) seen[a[i]] = true; гэж шалгана. n-ээс том тоо хариунд нөлөөлөхгүй.

  3. 3.Array-д тоо нэг нэгээр нэмэгдэх бүрт MEX-ийг хэвлэ. Нийт хугацаа O(n) байх ёстой.

    Hint харах

    Тоо нэмэгдэхэд MEX хэзээ ч буурахгүй.

    Хариу ба тайлбар

    m-ийг тоо бүрийн дараа тэглэхгүй. Шинэ тоог тэмдэглээд while (seen[m]) m++; гэж үргэлжлүүлнэ. m нийтдээ n-ээс илүү нэмэгдэхгүй тул O(n).

Жишээ

Оролт

7
3 0 1 5 1 2 7

Гаралт

4