Определение первого доступного значения в списке целых чисел

Question

Я получил простой список целых чисел.

List<int> myInts = new List<int>();

myInts.Add(0);
myInts.Add(1);
myInts.Add(4);
myInts.Add(6);
myInts.Add(24);

Моя цель - получить первое неиспользуемое (доступное) значение из списка.

(первое положительное значение, которого еще нетприсутствует в коллекции)

В этом случае ответ будет 2.

Вот мой текущий код:

int GetFirstFreeInt()
{
    for (int i = 0; i < int.MaxValue; ++i)
    {
        if(!myInts.Contains(i))
            return i;
    }

    throw new InvalidOperationException("All integers are already used.");
}

Есть ли лучший способ?Может быть, с помощью LINQ?Как бы вы это сделали?

Конечно, здесь я использовал int для простоты, но мой вопрос может относиться к любому типу.

Answer 1

В основном вам нужен первый элемент из последовательности 0..int.MaxValue, который не содержится в myInts:

int? firstAvailable = Enumerable.Range(0, int.MaxValue)
                                .Except(myInts)
                                .FirstOrDefault();

Изменить в ответ на комментарий:

Здесь нет снижения производительности здесь для итерации до int.MaxValue. Linq собирается внутренне создать хеш-таблицу для myInts, а затем начать итерацию по последовательности, созданной Enumerable.Range() - как только будет найден первый элемент, не содержащийся в хеш-таблице, получим целое число методом Except() и возвращается FirstOrDefault() - после чего итерация останавливается. Это означает, что общее усилие составляет O (n) для создания хеш-таблицы, а затем худший случай O (n) для итерации по последовательности, где n - число целых чисел в myInts.

Подробнее о Except() см., Например, серию EduLinq Джона Скита: Переопределение LINQ для объектов: Часть 17 - За исключением

Answer 2

Ну, если список упорядочен от наименьшего к наибольшему и содержит значения от 0 до положительной бесконечности, вы можете просто получить доступ к i-му элементу.if (myInts[i] != i) return i;, который по сути будет таким же, но не требует повторения списка для каждой и каждой проверки Contains (метод Contains выполняет итерацию по списку, превращая ваш алгоритм в O (n-квадрат), а не O(п)).