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 5

    3

    Với a = [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 3

    5

    Với a = [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;
}