Нахождение минимального элемента, который не принадлежит заданному множеству

#алгоритм

Задание:


  дан массив A из N элементов. Написать функцию LOST(A) – минимальное целое t >=0,
такое что t <> Aj, для всех j в массиве. 


Хочу найти оптимальное решение этой проблемы.
Данную задачу я пытался решить сам, вот мой код 

#include  
using namespace std;
int lost(int i, int k, int *a)
{
    int t = 0;
    for (int j = 0; j < k - i + 1; j++)
        for (int l = i; l <= k; l++)
            if (t == a[l])
            {
                t++;
                break;
            }
    return t;
}

int main()
{
    int n;
    cin >> n;
    int *array = new int[n];
    for (int i = 0; i < n; i++)
        cin >> *(array + i);
    int i, k;
    cin >> i >> k;
    cout << lost(i, k, array);
    return 0;
}

    

Ответы

Ответ 1

Минимальное отсутствующее значение t >= 0 в наборе из N значений всегда будет принадлежать
диапазону [0, N]. Поэтому O(N) решение вашей задачи сводится к заведению массива из
N флагов (изначально нулевых)

bool F[N] = { 0 };


проходу по исходным значениям A[j] и выставлению флагов для присутствующих значений
(игнорируя те значения, которые больше или равны N) 

for (unsigned j = 0; j < N; ++j)    
  if (A[j] < N) 
    F[j] = 1;


и затем поиску первого нулевого флага в этом массиве флагов. Позиция этого первого
нулевого флага - это и есть минимальное отсутствующее значение. Разумеется, если все
флаги в массиве являются ненулевыми, то минимальное отсутствующее значение равно N.

Готово.

"Остроумным" считается не заводить дополнительный массив флагов, а использовать для
этой цели сам массив A[j] (если его разрешается модифицировать) путем какой-то "пометки"
элементов (замены положительных на отрицательные и т.п.), но это уже непринципиальное
пионерство.