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

У меня есть простой список ints.

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? Как вы это сделаете?

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

Ответы

Ответ 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() см., например, версию Jon Skeet EduLinq: Повторное использование LINQ для объектов: часть 17 - кроме

Ответ 2

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