CTDL và giải thuật - In số tự nhiên nhỏ nhất chưa xuất hiện trong dãy
Bài tập.
Cho một dãy a
gồm n
số tự nhiên. In số tự nhiên nhỏ nhất chưa xuất hiện trong dãy.
Ví dụ:
- Test mẫu 1:
Input Output 4
0 1 2 53
Vớia = [0, 1, 2, 5]
thì kết quả mong muốn là3
.
- Test mẫu 2:
Input Output 7
0 0 1 4 2 4 35
Vớia = [0, 0, 1, 4, 2, 4, 3]
thì kết quả mong muốn là5
.
Hướng dẫn bài tập.
Ý tưởng: Sắp xếp dãy a thành dãy tăng dần, sau đó kiểm tra các phần tử kề nhau.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<math.h>
using namespace std;
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
int solve(int a[], int n){
quickSort(a, 0, n-1);
if (a[0] > 0) return 0;
for (int i = 1; i < n; i++){
if (a[i] - a[i-1] > 1){
return a[i-1] + 1;
}
}
return a[n-1] + 1;
}
int a[100001];
int main()
{
int n, k = 0;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
cout << solve(a, n);
return 0;
}