найти первую доступную длину в списке

#c# #list #long-integer

#c# #Список #long-целое число

Вопрос:

хорошо, это должно быть интересно.

предположим, у меня есть следующий код:

в этом примере первым доступным номером будет 2 .

List<long> myList = new List<long>(){0,1,10,3};

в этом примере первым доступным номером будет ‘4’.

List<long> myList = new List<long>(){0,1,2,3};

есть идеи?

1. Всегда ли числа начинаются с 0? Собираетесь ли вы изменить список и запросить первый доступный номер позже?

2. числа всегда будут начинаться с нуля, и список обязательно будет изменен позже.

Ответ №1:

Итак, под «доступным» вы подразумеваете «наименьшее неотрицательное число, которого еще нет в списке»?

У меня возникнет соблазн написать что-то вроде:

 HashSet<long> existing = new HashSet<long>(list);
for (long x = 0; x < long.MaxValue; x  )
{
    if (!existing.Contains(x))
    {
        return x;
    }
}
throw new InvalidOperationException("Somehow the list is enormous...");

РЕДАКТИРОВАТЬ: В качестве альтернативы вы можете упорядочить список, а затем найти первое значение, где индекс не совпадает со значением…

 var ordered = list.OrderBy(x => x);
var differences = ordered.Select((value, index) => new { value, index })
                         .Where(pair => pair.value != pair.index)
                         .Select(pair => (int?) pair.index);
var firstDifference = differences.FirstOrDefault();
long nextAvailable = firstDifference ?? list.Count;

Последняя строка предназначена для устранения ситуации, когда список непрерывен с 0. Другой альтернативой было бы:

 var nextAvailable = list.Concat(new[] { long.MaxValue })
                        .OrderBy(x => x)
                        .Select((value, index) => new { value, index })
                        .Where(pair => pair.value != pair.index)
                        .Select(pair => pair.index)
                        .First();

Это должно быть нормально, если список не содержит long.MaxValue 1 элементов, чего не может быть в текущих версиях .NET . (Это много памяти …) Честно говоря, у этого уже будут проблемы, когда он выйдет за пределы int.MaxValue элементов из-за Select части, принимающей int индекс…

1. ваше второе предложение содержит ошибку в последней строке, ?? в этом случае оно не может быть применено.

2. @Dementic: исправлено, спасибо — я использовал FirstOrDefault неправильное выражение.

3. в конце я использовал ваши 3-е методы, так как мне просто нравится Lambda Linq.

Ответ №2:

 list.Sort();

var range = Enumerable.Range( list.First(), list.Last()- list.First());

var number = range.Except(list).FirstOrDefault();