Найти минимальный элемент, отсутствующий в последовательности неотрицательных целых чисел

Question

Мне нужно найти минимальный недостающий элемент из последовательности неотрицательных целых чисел.

Пример: у меня есть: 0 5 10 4 3 1

The missing element is 2.

В приведенной выше последовательности недостающими элементами являются 2 6 7 8 9. Минимум среди них 2, поэтому ответ 2.

Грубая сила. Я отсортирую последовательность и получу минимальный элемент в nlogn. Я ищу лучшее решение. Любая помощь?

Answer 1

Нет необходимости в сортировке.

1. Перейдите по списку и найдите 2 самых маленьких значения, разница между которыми больше 1. (O (N))

2. Распечатать (найдено наименьшее значение) + 1.

Answer 2

псевдокод:

for(int i = 0 ; i < Int.MAX ; i++)
{
   if(i is not in list)
   {
       return i
    }
}

Конечно, возможно, это можно оптимизировать, но в качестве первоначального черновика, чтобы сдать ваши тесты (у вас есть тесты, верно), это очень простое решение, которое даст вам уверенность в том, что ваши тесты правильно, освобождая вас для оптимизации при необходимости.