Tìm MEX của dãy
Xem dạng PDF
Gửi bài giải
Điểm:
0,00
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
64M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++
Đề bài: Cho một dãy ~a~ gồm ~n~ phần tử (~1 \leq n \leq 10^5~, ~1 \leq a_i \leq 10^9~). Tìm ~\text{MEX}(a)^\dagger~.
~\dagger~ MEX (minimum excluded integer) của 1 dãy là số nguyên không âm nhỏ nhất không xuất hiện trong dãy đó. Ví dụ: MEX của ~[0;1;4;5]~ là ~2~, MEX của ~[2;0;3;4]~ là ~1~.
Debug code sau:
#include <bits/stdc++.h>
using namespace std;
int mex (vector<int> &a, int n) {
vector<bool> check(n + 1);
for (int i : a)
if (i <= n) check[i] = 1;
for (int i = 1; i <= n; i++)
if (!check[i]) return i;
return n + 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> a(n);
for (int &i : a) cin >> i;
cout << mex(a, n);
return 0;
}
Bình luận