Найти пропущенные и перекрывающиеся числа в последовательностях

Question

Допустим, у нас есть такая структура данных:

var sequences = new List<Tuple<int, int>>
                {
                    new Tuple<int, int>(1, 10),
                    new Tuple<int, int>(8, 101),
                    new Tuple<int, int>(102, 103),
                    new Tuple<int, int>(104, 104),
                    new Tuple<int, int>(110, 200)
                };

Я хотел бы получить два результата из этой коллекции:

• Все пропущенные числа (в этом примере: 105, 106, 107, 108, 109)
• Все перекрывающиеся числа (в этом примере: 8, 9, 10)

Я мог бы написать алгоритм с паройпетли и вспомогательные коллекции.Этот курс будет работать, но мне интересно, можно ли это сделать с помощью LINQ и / или других более простых и коротких алгоритмов?

Редактировать: Моя структура данных из приведенного выше примера представляет 5 последовательностей, первыйодин содержит числа от 1 до 10, второй содержит числа от 8 до 101 и т. д. Так как в производстве последовательности могут быть намного больше (до миллионов), они не представлены в фактической коллекции (дляэкземпляр со списками со всеми числами), но с кортежами, которые представляют минимальное и максимальное число каждой последовательности.

Answer 1

Вы можете сделать это через

var missing = 
      Enumerable.Range(1, 200)
               .Where(i => sequences.All(t => t.Item1 > i || t.Item2 < i));
var overlapping = 
      Enumerable.Range(1, 200)
                .Where(i => sequences.Count(t => t.Item1 <= i && t.Item2 >= i) > 1);

Answer 2

Я знаю алгоритм для этой проблемы (это псевдокод). (Классы сложности O(nlog(n)), где n - количество кортежей)

Таким образом, решение сортирует Tuple по функции:

  int comparer( Tuple a, Tuple b) {
      if ( a.first.compareTo(b.first) == 0 ) {
          return a.second.compareTo(b.second);
      } else 
          return a.first.compareTo(b.first);
  }

поэтому пример кортежа: (1, 10), (1, 5), (2, 8) будет отсортирован по: (1,5), (1, 10), (2, 8).

Следующим шагом является накопление этого результата. Повторите этот результат и:

 Tuple result = SortedList[0];
 foreach ( Tuple tuple in SortedList ) {

     if ( result.second < tuple.first ) {

        // here you have missing number (result.second, tuple.first)

        result.first = tuple.first; 
        result.second = tuple.second
     } else if ( result.second > tuple.first ) {

        // here you have overlapping number (tuple.first, min( result.second,tuple.second ))

        if ( result.second < tuple.second ) {
              result.second = tuple.second;
        }
     } else {
        result.second = tuple.second;
     }

 }

Что мы знаем, что если будет повторяться следующий кортеж, то первое число будет больше или равно result.first. Комментируйте в коде, сообщайте, где у вас перекрывающийся и отсутствующий номер

Answer 3

Есть несколько крайних случаев, я могу только предположить, как вы хотите справиться.Я решил не обрабатывать один из них (прокомментировано в коде).Поскольку вы не указали, как бы вы хотели представлять отсутствующие / пересекающиеся последовательности, я выбрал свой собственный формат, используя кортежи для определения начала и конца последовательности.

Answer 4

За один проход:

var sequences = new List<Tuple<int, int>>
    {
        new Tuple<int, int>(1, 10),
        new Tuple<int, int>(8, 101),
        new Tuple<int, int>(102, 103),
        new Tuple<int, int>(104, 104),
        new Tuple<int, int>(110, 200)
    };
var missing = new List<int>();
var overlap = new List<int>();

sequences.Aggregate((prev, current) => {
    if (prev.Item2 >= current.Item1) {
        overlap.AddRange(Enumerable.Range(current.Item1, prev.Item2 - current.Item1 + 1));
    }
    if (current.Item1 > prev.Item2 + 1) {
        missing.AddRange(Enumerable.Range(prev.Item2 + 1, current.Item1 - prev.Item2 - 1));
    }
    return current;
});

Answer 5

попробуйте

var expandedSequences = sequences.Select(t => Enumerable.Range(t.Item1, t.Item2-t.Item1)).SelectMany(t => t).OrderBy(i => i);
var dupes = expandedSequences.GroupBy(i => i).Where(g => g.Count() > 1).Select(g => g.Key);
var missing = Enumerable.Range(expandedSequences.Min(), expandedSequences.Max()).Except(expandedSequences);