Найти отличное от других число

425

26 февраля 2017, 08:52

Есть последовательность различных int чисел. Необходимо эффективно найти любое int число, отличающееся от данных. Считаем, что такое число существует.

Answer 1

Находим максимальное, прибавляем 1. O(n).

int x = max_element(begin(array),end(array));

Минус - теоретически возможно, что в массиве есть одновременно минимальное/максимальное представимые значения...

Если структура отсортированная - сразу смотрим минимальное/максимальное значения, если они не минимальное/максимальное представимые - берем на 1 меньше (соответственно, больше), итого - O(1).

Если они минимальное/максимальное представимые - идем до первого "просвета", берем его. O(n).

В общем случае меньше чем за O(n) не вижу вариантов...