查找序列中缺失和重叠的数字

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

有一些边缘情况我只能假设你希望如何处理。我选择不处理其中之一（在代码中注释）。由于您没有给出如何表示丢失/重叠序列的指示，因此我选择了您自己的格式，使用元组来标识序列的开始和结束。

//Assumes they are sorted on item1
        Tuple<IEnumerable<Tuple<int,int>>,IEnumerable<Tuple<int,int>>> FindMissingAndOverLapping(IEnumerable<Tuple<int,int>> sequences){
            var previous = Tuple.Create(0, 0);
            var missing = new List<Tuple<int,int>>();
            var overlapping = new List<Tuple<int, int>>();
            var max = 0;
            foreach (var sequence in sequences){
                var end = previous.Item2;
                max = end > max ? end : max;
                if (previous.Item2 < sequence.Item1 + 1){
                    missing.Add(Tuple.Create(previous.Item2 + 1, sequence.Item1 - 1));
                } else if (max < sequence.Item1){
                    overlapping.Add(Tuple.Create(sequence.Item1, max));
                }
            }
            //The sequences in ovrelapping can be ovrelapping them self
            return new Tuple<IEnumerable<Tuple<int,int>>,IEnumerable<Tuple<int,int>>>(missing, overlapping);
        }

Answer 2

你可以通过

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 3

我知道这个问题的算法（它是伪代码）。 （复杂度类 O(nlog(n)) 其中 n 是元组的计数）

因此解决方案是按函数对元组进行排序：

  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 4

试试这个

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);

Answer 5

一次性完成：

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;
});