3

Задание:

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

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

#include <iostream> 
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;
}
0

1 ответ 1

4

Минимальное отсутствующее значение 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] (если его разрешается модифицировать) путем какой-то "пометки" элементов (замены положительных на отрицательные и т.п.), но это уже непринципиальное пионерство.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.